Наскоро имах един доста труден проблем за интервю с 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.
Добре, сега можете да опитате да подходите към проблема. По-долу предоставям мое собствено решение, което беше признато за най-добро сред кандидатите от представителя на работодателя.
По принцип проблемът не трябва да бъде решен директно чрез използване на вложени цикли, защото това ще отнеме много време и няма да удовлетвори изискванията. Следователно трябва да се направи нещо друго, за да се опрости алгоритъмът. Моето решение се състоеше от две идеи:
- Първият съвет е да използвате знанието за времето. Трябва да намерим редица стойности, преминаващи към текущия инцидент. След като данните са сортирани, можем да гледаме само назад, което е добре.
- Трябва да внедрим персонализирани броячи, които ще ни позволят да съхраняваме стойностите, които са ни необходими за резултат. Използването на броячи е обичайна практика в програмирането и тук ще ни позволи да използваме само един цикъл итериращ върху данните. Как работи?! Нека го обясня просто. Инициализираме два брояча: глобален и локален. Глобалният брояч итерира всички данни, съхранявайки текущия инцидент на разглеждане. Локалният брояч отива назад и съхранява броя на стойностите назад, които отговарят на условията (използвайки цикъл while). Ще разберете, че е ясно, като разгледате кода.
Трябва да отбележа, че изпратих две решения:
В първия сортирах данните само по време и проектирах алгоритъма да поддържа добавяне на нови данни (по-късни инциденти във времето). Това изискваше от мен да внедря някакъв вид памет, съхраняваща данни в матрици на функции M по M. Изпълнението на алгоритъма изглеждаше около 12 секунди.
Във втория изоставих идеята за внедряване на знания (защото [1] M може да бъде огромно, [2] наличието на такава функционалност не се изисква от задачата). Сортирах стойностите по всички колони. Идеята за броячите беше запазена. Изпълнението на алгоритъма беше около 4 секунди.
Освен това използвах пакета Numba, за да компилирам в алгоритъм на език за програмиране C, за да го ускоря възможно най-много.
Кодът е даден по-долу.
Използвани зависимости 📚:
Решение 1 (с памет) — 12 секунди производителност ✈️.
Решение 2 (супер бързо, но без памет) — 4 секунди производителност 🚀:
Моля, уведомете ме, ако сте намерили статията за полезна, като я аплодирате и оставите коментар. Благодаря.