Наскоро имах един доста труден проблем за интервю с Python за решаване, който реших да обясня тук, защото според мен е подходящ за някои реални сценарии на обработка на данни. Освен това не бях намерил никакви решения или обяснение на подобни задачи в мрежата, така че може да е полезно да споделя задачата с моето собствено решение.

Твърдо съм убеден, че ако положите усилия да го разрешите сами, ще се възползвате значително повече от тази статия, отколкото ако погледнете директно моето решение.

Това е проблемът:

Дадените данни са представени от N редове (точки с данни за инциденти) и 4 колони, които са: id, feature1, feature2, time. Id е уникален номер за всеки инцидент, feature1 и feature2 са две категорични характеристики (може да има категории M ), времето е времето, когато е възникнал инцидент, нормализирано от 0 до 1.

Данните могат да бъдат генерирани от следния код:

Кодът генерира някои данни, които изглеждат така:

Задачата е да се създаде функция на Python, която приема три входа:

1. Име на входния файл с данните,

2. M(брой категории),

3. dT(времева разлика),

и изчислява за всеки отN инциденти броя на инцидентите, които отговарят на следните условия:

1. Те са предшествали този инцидент във времето, но разликата във времето е по-малка отdT;

2. Те имат еднакви стойности наfeature1иfeature2.

Например, за показаните по-горе данни, акоdT= 0,3, отговорът (изход на функцията) трябва да бъде:

Форматът на входния файл на функцията, както и на изхода, трябва да бъде „csv“.

Основното изискване към алгоритъма — трябва да е бърз и да обработва данните от 1 милион реда със 100 категории и 0,3 времева разлика (M=100, N=1000000, dT=0,3) за по-малко от 1 минута (използвайки 1 core CPU) и консумират по-малко от 2 GB RAM.

Допълнителни изисквания (които не засягат алгоритъма) бяха:

Функцията трябва също да поддържа извикване от терминал. Когато се извика от терминал, той трябва да приеме следните аргументи:

1. Име на входния файл с данните;

2. Име на изходния файл с резултатите;

3. Стойност наdT.

Добре, сега можете да опитате да подходите към проблема. По-долу предоставям мое собствено решение, което беше признато за най-добро сред кандидатите от представителя на работодателя.

По принцип проблемът не трябва да бъде решен директно чрез използване на вложени цикли, защото това ще отнеме много време и няма да удовлетвори изискванията. Следователно трябва да се направи нещо друго, за да се опрости алгоритъмът. Моето решение се състоеше от две идеи:

  1. Първият съвет е да използвате знанието за времето. Трябва да намерим редица стойности, преминаващи към текущия инцидент. След като данните са сортирани, можем да гледаме само назад, което е добре.
  2. Трябва да внедрим персонализирани броячи, които ще ни позволят да съхраняваме стойностите, които са ни необходими за резултат. Използването на броячи е обичайна практика в програмирането и тук ще ни позволи да използваме само един цикъл итериращ върху данните. Как работи?! Нека го обясня просто. Инициализираме два брояча: глобален и локален. Глобалният брояч итерира всички данни, съхранявайки текущия инцидент на разглеждане. Локалният брояч отива назад и съхранява броя на стойностите назад, които отговарят на условията (използвайки цикъл while). Ще разберете, че е ясно, като разгледате кода.

Трябва да отбележа, че изпратих две решения:

В първия сортирах данните само по време и проектирах алгоритъма да поддържа добавяне на нови данни (по-късни инциденти във времето). Това изискваше от мен да внедря някакъв вид памет, съхраняваща данни в матрици на функции M по M. Изпълнението на алгоритъма изглеждаше около 12 секунди.

Във втория изоставих идеята за внедряване на знания (защото [1] M може да бъде огромно, [2] наличието на такава функционалност не се изисква от задачата). Сортирах стойностите по всички колони. Идеята за броячите беше запазена. Изпълнението на алгоритъма беше около 4 секунди.

Освен това използвах пакета Numba, за да компилирам в алгоритъм на език за програмиране C, за да го ускоря възможно най-много.

Кодът е даден по-долу.

Използвани зависимости 📚:

Решение 1 (с памет) — 12 секунди производителност ✈️.

Решение 2 (супер бързо, но без памет) — 4 секунди производителност 🚀:

Моля, уведомете ме, ако сте намерили статията за полезна, като я аплодирате и оставите коментар. Благодаря.