Як опрацювати CSV файл з 6 млн рядків?

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті

Є CSV файл в якому щось близько 6583257 рядків з описом певних товарів. Потрібно по двом критеріям знайти товари. Ці критерії це артикул і виробник. Потім серед груп товарів які мають однаковий артикул і виробника знайти товар з найменшою ціною а всі інші з цього набору однакових товарів видалити. Те що вийшло записати в CSV. Файл розміром більше 400 мебібайт. Що я придумав: групувати номера рядків по виробникам і артикулам і виходить два обєкта (один для виброників інший для артикулів) в яких містяться словники з назвами виробників або артикулів в якості ключа а в цих словниках є масив numbers з номерами рядків які містять товар з вказаним виробником або артикулом.

articles = {}
{
    # Всі рядки в яких є виробник prod1
    'prod1': {'numbers': [1,2,38555, 387]}
    'prod2': {'numbers': [33,22,355, 1000]}
}

Після збору даних даних ось що роблю: масив numbers кожного виробника порівняти з масивом numbers всіх артикулів і якщо перетин масивів містить більше одного елементу, додати цей масив номерів рядків до масиву з копіями. Використовую Пітонівську функцію intersection. Проблема в тому що програма виконується дуже довго і я так і не дочекався закінчення її роботи тому що час очікування наблизився до 5 годин. Скрипт в оперативці розрісся майже на 800 мебібайт. Ось шматок коду:

for brand in list(brands.keys()):
    # articles обєкт з артикулями
    result = find_duplicates(brands[brand]['numbers'], articles)
    if result:
        # id потрібне для групування номерів рядків
        id = hash(brand) + hash(result['article'])
        duplicates[id] = {'row_numbers': result['row_numbers']}

def find_duplicates(number_list, articles):
    result = {}
    for article, numbers in articles.items():
        for k2, number_array in numbers.items():
            matches = set(number_list).intersection(number_array)
            if len(matches) > 1:
                result['row_numbers'] = matches
                result['article'] = article
    return result
👍ПодобаєтьсяСподобалось0
До обраногоВ обраному0
LinkedIn

Найкращі коментарі пропустити

Dear Sir, I can do this manually for you in a week. Our team consists of great developers. We are new on this website. If you award us we don’t rest until the job done.

Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Чисто из интереса
У меня вышло 16 секунд

MS SQL 2016SP1
никаких индексов, решение в лоб
Breakdown
— table create (no indexes) — 0
— parallel bulk load into heap — 13 seconds
— determine positions with min price per group — 3 seconds

Hardware host vm E5-2660V2 (8 vCPU, 16 GB RAM, non raid SSD)
GrantedMemory for query — 1GB.

PS стрикли говоря задача поставлена криво

знайти товар з найменшою ціною а всі інші з цього набору однакових товарів видалити

если в группе brand + article есть несколько позиций с минимальной ценой ?

Не знаю. По ідеї це не має ніякого значення оскільки товари однакові.

3 секунды — это на тех кривых данных автора? Это как-то очень круто. Это прям с выдачей всех 2.5 млн строк результата?

Actually I did mistake. SSD for VM host was not local SSD. It was NAS attached drive.
I did one more test with import & processing on locally attached SSD

COUNT(*) - 2s (was 3s)
s018.radikal.ru/...​/1706/0e/887a8fa792b5.png
SELECT INTO new table — 5.5s
s018.radikal.ru/...​/1706/be/1cb502d6befd.png

PS If allocate 32vCPU for VM
time is dropping down for query #1 COUNT(*) to 800ms

Да, довольно быстро. А сколько времени создавалась tmp таблица и таки какой был размер результирующего множества?
Мне стало интересно попробовать на оракле без загрузки данных, с внешней таблицей, но шось с первой попытки все записи из набора данных автора оракл отверг.

Загрузка из файла в tmp через BULK INSERT — 13 секунд. Размер примерно такой же как и у сырого файла — около 0.5гб
Я думаю можно и быстрее, все на скорую руку.
Собственно чего я запостил результаты — для сиквела пара миллионов строк — это не множество даже, не смысла строить свои велосипеды. СУБД это как фреймворк — нужно уметь использовать.

С этим никто и не спорил. Другое дело, что вряд ли у автора прям сразу есть оракл или MS SQL, или даже постгрес. MySQL, SQLIte не поддерживают аналитику (насколько я знаю), то все равно потребуются какие-то промежуточные таблицы, но по идее, все равно должно быть в пределах нескольких минут (от загрузки до выгрузки).

и шо у тебя вышло ? в таких задачах основная заморочка — автоматизированное получение данных, проверка входных данных перед занесением в базу, что бы не было дубликатов и перепутанных колонок и контроль результатов. Ведь в реальных проектах эти данные каждый день обновляются и каждый день нужна свежая выборка. Запустить квори на сервере — это 3 процента от всего процесса.

Писатель, читать не пробовал ?

Проверка на дубликаты решается добавлением UNIQUE KEY на нужный набор столбцов + LOAD DATA LOCAL INFILE 'source.csv' IGNORE INTO TABLE...

Или льем в соседнюю таблицу, потом делаем INSERT INTO ON DUPLICATE KEY UPDATE в целевую

mysql> SELECT COUNT(*) FROM product;
+----------+
| COUNT(*) |
+----------+
|  1384514 |
+----------+
1 row in set (3.78 sec)

mysql> DROP TABLE IF EXISTS product_registry;
Query OK, 0 rows affected, 1 warning (0.00 sec)

mysql> CREATE TABLE product_registry SELECT vendor, prodid as `mpn`, pprice as `price` FROM product ORDER BY pprice ASC;
Query OK, 1384514 rows affected (7.31 sec)
Records: 1384514  Duplicates: 0  Warnings: 0

mysql> ALTER TABLE product_registry ADD KEY (vendor, mpn);
Query OK, 1384514 rows affected (10.52 sec)
Records: 1384514  Duplicates: 0  Warnings: 0

mysql> SELECT * FROM product_registry WHERE vendor = 'Lenovo' AND mpn = '40A50230EU' GROUP BY vendor, mpn;
+--------+------------+---------+
| vendor | mpn        | price   |
+--------+------------+---------+
| Lenovo | 40A50230EU | 208.450 |
+--------+------------+---------+
1 row in set (0.00 sec)

mysql> SELECT MIN(pprice) FROM product WHERE vendor = 'Lenovo' AND prodid = '40A50230EU' GROUP BY vendor, prodid;
+-------------+
| MIN(pprice) |
+-------------+
|     208.450 |
+-------------+
1 row in set (0.00 sec)

Далі експортуєте таблицю в CSV і вуаля:

$ mysql -h localhost -u user -p database -e "SELECT * FROM product_registry" > products.csv
SELECT * FROM product_registry WHERE vendor = ’Lenovo’ AND mpn = ’40A50230EU’ GROUP BY vendor, mpn;
кажись это не будет работать, потому что нада или по всем групать или контркетные поля выбирать

Тогда уберите WHERE... из запроса, и вы получите отчет по всем парам vendor/mpn с наименьшей ценой.

спочатку потрібно підготувати юзер сторіс! потім естімейшн, планування і т.д.

Planning Poker сессію забули.

ні, не забув :) це ж входить в естімейшн, або в «і т.д.»

Помився і ось шо придумав: читаємо номер рядка, артикул і назву виробника, обєднуємо виробнкиа і артикул, над цим новим рядком робимо md5 або щось таке. Виходить масив з обєктами в якого властивості з ідентифікаторами на зразок 1bc29b36f623ba82aaf6724fd3b16718 і властивіть row_number яка містить номера рядка де такий ключ зустрічається. Зі масива видаляємо всі обєкти з унікальними ідентифікаторами. Використовуючи номера рядків того що залишилося читаємо файл знову збираючи ціни, щалишаємо найнижчі ціни а всі інші щаносимо в чорний список, копіюємо дані в новий файл не чіпаючи рядки з номерами в чорному списку.

Подобное упорство достойно лучшего применения. Например, прослушать какой-то базовый курс по алгоритмам и структурам данных :) А задача решается намного проще и за линейное время, как-то так pastebin.com/Vz0crN0s

якщо тупо на php (memory_limit = 2G, PHP 7.0)

1065.46 Mbyte
Time: 156s

Phenom II X4 945

pastebin.com/E6PfAehb

якщо тупо на датабазє, то без додаткової фільтрації якось так:

sdb1=# copy tires from 'popsps.csv' delimiter ';' CSV HEADER
 ;
COPY 6508008
Time: 47457.157 ms
sdb1=# select count(*) from (select storage_code, article, brand, description, 
price, min(price) over (partition by brand, article) as minprice from tires ) t 
where price=minprice;
  count
---------
 2478663
(1 row)


Time: 54271.062 ms
sdb1=#

“Excel cannot exceed the limit of 1,048,576 rows and 16,384 columns.”

это ограничения для одного work-sheet!

Time: 54271.062 ms

да в 3 раза быстрее.

зато у меня — полное решение, даешь файл — получаешь нужный файл :)
я там кстати подкрутил по памяти, а то самого удивил такой перерасход.
запустил еще раз
Time: 156s — до записи на диск
674.6 Mbyte; 2388267
All time: 166s
интересно что у нас количество итоговых строк разное.

просто стало интересно — да что ж там топикастер мучится то??? а возьму ка я не шустрый пых, да по бытенькому.

Ну я не в плане соревноваться, мне кажется что скрипт на том же awk/sed должен быстрее отработать. Вот датасет реально трохи дебильный, такой нарочно и не придумаешь, по крайней мере, не выглядит учебной задачей.

Ну я не в плане соревноваться,

да я тоже не для этого.

если бы по скорости, то по идее в 2 потока на джаве, в одном чтение-парсинг, в другом работа с HashMap, должен бы показать хороший результат.
чтобы снизить оверхед на переключение-ожидание-блокировки, то первый поток должен помещать в общую очередь не по одной распарсенной строке, а пачку. ну и с hashCode() и equals() ResulItem’а надо будет сжульничать. Но это уже для соревнования с реализацией на plain C :)

мне кажется что скрипт на том же awk/sed должен быстрее отработать.

по идее да. если логику обработки удасться описать.
а вот если описание алгоритма для связки awk/sed окажется закрученным, то еще неизвестно, для общего случая.

С многопоточностью намучаетесь, и писать дольше будете, чем однопоточная — работать.

конечно. поэтому для парсинга обычно не только многопоточное, а и однопоточное не пишется на джаве, или c#, или еще чем нескриптовом, серьезном.

С многопоточностью намучаетесь

на самом деле там ничего сложного. все есть в системной библиотеке.
тонкость только — не загубить выгоды оверхедом от переключения потоков.

как-то делал тестовое, и для прикола в двух вариантах. по бытенькому не удалось добиться производительности многопоточного варианта выше чем у однопоточного! :)

Ви ще́ тут!? =) Терміново вчіть SQL, схоже це дуже добре впишеться у стек ваших навичок.

На скільки я зрозумів вашу задачу, вам треба

1. Знайти мінімальне значення ціни по кожному артикулу.
2. Зв’язати отриманий результат із повною таблицею, і результат вставити у новий CSV-файл.

Покрокова інструкція:
1. Якщо ви на Windows, скачуєте SQLite3, розархівовуєте його в ту теку, де ви будете працювати з даними.
2. У цій же теці створюєте файл csv-to-sqlite.sql, вставляєте у нього наступний скрипт.
3. Читаєте коментарі й дієте відповідно (зокрема вам треба перейменувати назву сирцевого файла і поля з нього).
4. запускаєте скрипт sqlite3 < csv-to-sqlite.sql

Сам скрипт:

-- Назва такого файла автоматично з'явиться у вас у поточній теці - це файл бази даних
.open 'db.sqlite'
.mode csv

-- Видаляємо стару таблицю
drop table if exists raw_data;

select '('||time('now','localtime')||') Імпортуємо дані із CSV у таблицю raw_data';

.import source-file.csv raw_data

select '('||time('now','localtime')||') Переливаємо дані у таблицю data з правильними типами даних';

-- Вам тут (і далі) треба замінити мої назви полів на назви полів точно як вони називаються у CSV-файлі,
-- ще треба пододавати інші поля
-- У мене тут article - це артикул, price - ціна, customer - назва виробника
create table if not exists data
(
  article integer
  ,price integer
  ,customer text
);

-- Видаляємо старі дані
delete from data;

-- Переливаємо дані із таблиці raw_data у таблицю data
insert into data select * from raw_data;

-- Тут треба замінити лише назви полів, але не їхню кількість
create table if not exists tmp
(
  article integer
  ,price integer
);

-- Видаляємо старі дані
delete from tmp;

select '('||time('now','localtime')||') Створюємо індекси для таблиці data';

create index if not exists i_price on data(price);
create index if not exists i_article on data(article);

select '('||time('now','localtime')||') Вибераємо мінімальну ціну у таблцю tmp';

insert into tmp
select
  article
  ,min(price) as price
from raw_data as t
group by article;

select '('||time('now','localtime')||') Створюємо індекси для таблиці tmp';
create index if not exists i_price on tmp(price);
create index if not exists i_article on tmp(article);

select '('||time('now','localtime')||') Зливаємо результат у файл result.csv';

-- Результат виконання наступного запиту вставиться у файл result.csv
.output 'result.csv'

select d.*
from data as d
  join tmp as t
    on d.article = t.article
      and d.price = t.price
;

.output stdout

select '('||time('now','localtime')||') Фініш';

.exit

Писав скрипт перед сном, зараз бачу помилку. Замініть ось цю частину:

-- Вчора я помилився, бо брав дані з таблиці raw_data, а треба з таблиці data
insert into tmp
select
  article
  ,min(price) as price
from data as t
group by article;

По таким фразам вираховується вата, бо вона пише без аргументів.

Окей, с аргументами.
1. Какая здесь вообще решается задача? У автора группировка по артикулу и производителю ака brand.
2. Зачем данные бессмысленно гонять между таблицами?
3. Зачем создавать индексы на таблице tmp (я уже не говорю о смысле этой таблицы, она бессмысленна)? 3.1. Зачем создавать два индекса??

Терміново вчіть SQL

Такое же пожелание Вам самому, зачем использовать что-то, чего не очень понимаете?

Саша, я працював адміном MS SQL, MySQL у двох банках. Ви мене ще будеде вчити SQL?

1. Ви очевидно пробіглись галопом по скрипту без розуміння елементарних SQL-команд. Я роблю групування якраз по артикулу. По виробнику групувати взагалі немає сенсу.

2. Дані можна було б і не ганяти, якщо б цим займався я сам, бо зразу б заганяв дані у таблицю з правильними типами даних. Але оскільки я пишу інструкції для людини, яка не шарить у цьому, то простіше загнати дані як вони є, а потім у таблицю з правильними типами даних.

3. Індекси створюються, бо йде зв’язування двох великих таблиць. Створюються два індекси, бо зв’язування відбуваються саме по цим полям.

Саша, я працював адміном MS SQL, MySQL у двох банках. Ви мене ще будеде вчити SQL?

Не, учить имеет смысл если есть желание учиться)

1. Ви очевидно пробіглись галопом по скрипту без розуміння елементарних SQL-команд. Я роблю групування якраз по артикулу. По виробнику групувати взагалі немає сенсу.

1. Это если артикулы являются уникальными и не повторяются для разных производителей, из условия это непонятно, а глядя на реальные данные, я бы на это не рассчитывал.
2. Зачем? В задаче требуется выгрузить всю эту хню в тот же CSV, реальные-то данные пробовали? Сколько ресурсов уйдет на бессмысленные верификации, и главное. а что делать с данными типа count_text= ’>40′?
3.

create index if not exists i_price on tmp(price);
create index if not exists i_article on tmp(article);

Таблица tmp будет просмотрена полностью, какой смысл создавать индекс(ы)? В каком случае использование индекса может быть эффективно?
В каком случае СУБД (любая практически) сможет заиспользовать два индекса одновременно и в каком случае такой доступ может быть эффективным?

Тут реально предлагали разные способы, но зачем предлагать такое?

1. Артикули повинні якраз повторюватись для усіх виробників (для одного конкретного товару один відповідний артикул, що повторюється у всіх виробників), вони повинні бути універсальними для всіх. В противному разі нічого не вийде взагалі.

2. Оскільки CSV-файл, швидше за все, із заголовками у першому рядку, то їх вставка у готову таблицю з правильними типами даних могла б призвести до помилки, оскільки ці заголовки могли потрапити у поле з типом даних integer, наприклад.

Реальні дані? Десь тут є лінк на реальні дані? Чи ви про тестові дані? Я перевіряв на своїх тестових даних.

«Безсмысленные верификации» — Ви про що? Про те, що поля з текстових даних переганяються у поля з числовим типом даних? А ви уявили як ви будете мінімальне значення отримувати з текстових даних? У вас би 111 було меншим за 12.

3. Ще раз, tmp таблиця ймовірно буде великою. Також, ми маємо справу з великою таблицею з необробленими вхідними даними. Щоб зв’язати дві великі таблиці, треба створювати індекси по тим полям, по яким буде ця зв’язка.

Щоправда, тут можна було б створити один індекс з двома полями, але це вже тонкі деталі. Я не приділяв багато часу на оптимізацію цього скрипта, можна було б і одним індексом обійтись.

Костя, читаем условие:

Потрібно по двом критеріям знайти товари. Ці критерії це артикул і виробник. Потім серед груп товарів які мають однаковий артикул і виробника знайти товар з найменшою ціною
1. Артикули повинні якраз повторюватись для усіх виробників, вони повинні бути універсальними для всіх. В противному разі нічого не вийде взагалі.

Берем простой набор данных:
art;brand;price
7;Nokian;2186.23
7;Nokian;2286.54
7;Yokohama;2172.94
Группировка по артикулу даст одну строку с 2172.94, группировка по артикулу и производителю даст две строки. Разница есть?
2. Ссылка на тестовый набор данных буквально ниже:

Файл: www.dropbox.com/...​7snndutey/popsps.csv?dl=1

Ну вот только цена должна распознаться как число, для остальных данных это вообще не нужно, это потеря времени и ресурсов.

3. Ще раз, tmp таблиця ймовірно буде великою. Також, ми маємо справу з великою таблицею з необробленими вхідними даними. Щоб зв’язати дві великі таблиці, треба створювати індекси по тим полям, по яким буде ця зв’язка.

Костя, эти комменты говорят о Вашей компетентности намного больше чем сам скрипт в самом начале. Я реально советую перестать комментировать и хотя бы почитать что-нибудь на тему планов выполнения, методов доступа к таблицам, методов соединения наборов данных, оптимизатора и оптимизации запросов.

1. Ок, я неуважно прочитав що по-суті нам треба мінімальна ціна в розрізі конкретного виробника. Каюсь. Хоча скрипт зміниться в одному-двох рядках. Без реальних даних перед очима, важко написати правильний скрипт з першого разу.

2. «Ну вот только цена должна распознаться как число» — Ви так говорите, наче без цього можна було обійтись.

3. Планів виконання запитів я перечитав придостатньо, знаю про що я пишу, не треба мені розповідати про мою компетентність.

Константин,

1. Исходные данные — текстовой файл. На нем есть какие либо констрейнты гарантирующие
что brand + article = unique ? Нет — значит группировать обязательна.
2. Спорно, если задача того не требует — зачем привносить сложность ?
3. Очень странная стратегия индексации. Эффективней было бы иметь копозитный кластерный по обоим полям на обоих таблицах для MERGE JOIN на плане. Причем на таблице tmp он еще и UNIQUE будет.

PS good DBA != good DBE

1. Теска, я писав скрипт приблизно о першій годині ночі, коли вже збирався лягати спати, після робочого дня. Очевидно що автор повний нуль в SQL, тому хоча я й бачив, що він написав начебто, що треба шукати товари по двом критеріям, але я подумав, що ми маємо справу з універсальним артикулом, коли, наприклад, товар «хліб Батон» має єдиний артикул для усіх виробників. У мене не було перед собою даних, я гадав що там насправді є і не вгадав.

Якщо прочитати які задачі я ставив перед собою у тих двох пунктах перед скриптом, то я їх виконав як належить.

2. Ще раз кажу, я робив спрощено як для людини, яка могла й не знати що робити у випадку збою. А збій таки міг бути, якщо б дані вставлялись разом з першим рядком, де могли бути текстові заголовки (назви полів). Та перегонка з однієї таблиці в іншу коштувала б зайвих 400 МБ місця на жорсткому диску, і пару хвилин часу. — Це не велика жертва.

3. Так, згоден із тим що раціональніше створити один індекс по двом полям, а не два індекси. Це я зрозумів зразу на другий день зранку, після того як перечитував свою відповідь. Це також, прямо скажемо, дрібничка.

П.С. З дискусії в цій темі, роблю висновок, що таки треба професійний майданчик, щоб люди могли помірятись своїми... кхм... навичками.

Это такая редкость когда на доу появляется «код»...
Если уйдешь — останется только лайкать та котиков обсуждать

таки треба професійний майданчик, щоб люди могли помірятись своїми... кхм... навичками

такі вже є, це SO і quora

Здається на хабрі (чи на їх супутніх ресурсах) робили опитування по рівню знань англійської мови. Так от, більшість ІТ-шників зможуть читати англійською технічну документацію, бо вони звикли це робити, але вже що стосується переписки англійською, то таких назбирається не більше 30%.

Як би там не вихвалялись багато хто, але англійська мова десь для 70% ІТ-шників недоступна для безпроблемної переписки, коли треба описувати якісь нетривіальні професійні речі.

У мене на англійському stackoverflow більше 700 балів репутації, але коли треба щось там написати, то без гугл-транслейта не обійтись.

Ну і на stackoverflow формат не той, де можна розгорнуто подискутувати.

а я все думаю, че банки так плохо работают — а то в них люди скрипты в 1 ночи пишут и невнимательно читают условия, да и индексы повешены на поля как то не понятно, нафига там индексы по цене ?

нафига там индексы по цене

Коли будете мати елементарні знання по SQL, тоді у вас буде грунт, завдяки якому можна буде робити оцінку моїй компетентності. Щоб зрозуміти нафіга там індекси, треба мати саме елементарні знання з SQL. Ви вже другий у цій дискусії «експерт», який не розуміє «нафига там индекcы».

Костя, я уже задавал этот вопрос, но я могу задать еще раз.

В каком случае использование индекса может быть эффективно?

Предположим, что создан таки составной индекс на таблице tmp по двум полям, и предположим что и на основной таблице такой же индекс (на хиба только, непонятно) и при наличии двух альтернативных методов доступа к таблице в каком случае индексный доступ (неважно даже какой конкретно) будет эффективнее FTS?

Імпортування в SQLite займає дуже багато часу.

При умовній середній довжині рядка, 6 млн. вставляються 2.5 хвилини.

Написав майже те саме (замість ключів використовую конкатенацію виробник + артикула замість hash в Python) на VB.NET 2008. Працює швидше. Оперативноє пам’явті використовує максимум блищьк 330 мебібайт, накидать форму справа декількох хвилин на відміну від Tkinter. За три години майже добралося до 3 млн.

Файл: www.dropbox.com/...​7snndutey/popsps.csv?dl=1
Програма: pastebin.com/MpWBhLWg

Может еще скинете пример параметров для поиска интересно сколько времени займет набросать скриптец на разных языках и сколько времени пойдет на выполнение.

У вас поиск по параметрам артикул и производитель, вот интересно с ними посмотреть, что выйдет по времени.

Вот, не далее как сегодня утром, свеженькая статья. Как раз в тему
machinelearningmastery.com/...​a-files-machine-learning
Посмотрите, может и найдете себе метод «по вкусу».

csv файл размером 14Gb с 102715839 строками.
Время импорта в mysql при помощи load data 2:24 часа (вместе с построением индексов)
CPU E5-2685 + raid0 из intel ssd 3600
итоговая таблица в mysql 16,4 Гб

Это я так понимаю на базовом конфиге mysql ? Просто помнится подобные базы загружал быстрее без ссд и рейда, но «игрался» с параметрами сервера.

конечно не на базовом. Да и не mysql там, а mariadb. Узкое место — cpu. При load data используется лишь одно ядро. Эксперимены с загрузкой в множество потоков не дали результатов типа «ух ты как быстро» на innodb. Поэтому load data на aria engine.

Можно тремя запусками фильтров, обрабатывается по 1 строке:
1) на входе — полная таблица, на выходе — строки с данным артикулом
2) на входе — выхлоп из 1, на выходе — строки с данным производителем
3) на входе — выхлоп из 2, на выходе — минимальная цена
Можно либо питоном, либо sed, либо С++ (для извращенцев).
Можно сбрасывать результаты в файлы, можно — попытаться соединить пайпами.
По скорости — на питоне будет в 3 раза медленнее, чем на С++ или sed. На PyPy будет на 30% медленнее, чем на С++. Когда-то заспорили о производительности, и гоняли через них подобную задачу — выбор максимумов и минимумов в столбцах. Уходило 3.5 минуты на 10 GB, кажется.

Я бы на С за час написал программку. Таблица с индексом производителей (текст -> id, в таблице товаров id), таблица с индексом артикулов, после этого сами товары превращаются в контексте задачи в 3 инт числа (id производителя, id артикула, номер строки товара). Сортируем его qsort по id артикула сохраняя связность списков, и дальше элементарно.
Чтение файла и построение таблиц — на глаз минут 5, сортировка и выгрузка результата — еще пара минут.

Як зберегти зв’язанність списків і як генерувати id?

Наверняка есть стандартные способы это делать, но я когда-то написал свою имплементацию qsort, ей иногда и пользуюсь — там где в ней идут операции с элементами массива, выполняю одинаковые для всех списков где нужно сохранить связность.
Генерировать id — я бы советовал освоить map, id первого неизвестного слова = 1, если новое слово не найдено в map — добавить туда с id на единицу большим

пару производителя и артикул можно индексировать и одним числом если строки обьединить.

да, но по-моему это уже усложнит чтение кода, без заметных плюсов по памяти/скорости

Ну как же. 30% эконимия в оперативке да и сортировать проще по 1 столбцу. А вообще читать файл дважды не оптимально. Уж лучше пройтись по файлу 1 раз заполнив HashMaр. А затем сохранить его на диск. Если хешмап будет размером в 5мнл. элементов то сложность программы будет около О(1) на заполнение хешмапа+ О(1) на чтение.

Только не 30%, а хорошо если 5%. Ведь у нас в оперативке все строки еще лежат — цель выдать подмножество из них, а не просто сказать номера

Ну держать в оперативке 6 млн. записей слишком расточительно. Если 1 запись будет больше 600 байт, то 600*6000000 = 3,6Гбайт. 32-х разрядный комп уже не сможет адресоваться в таком объеме памяти. Я думал вы будете для каждой записи хранить по три int — а. Индекс товара, стоимость и номер строки в исходном файле. А после сортировок и удалений ненужных элементов используя этот массив пройтись еще 1 раз по файлу и построчно переписать его в выходной пропуская ненужные строки. Такой алгоритм и 100 млн. записей потянет.

Ну держать в оперативке 6 млн. записей слишком расточительно.

а не надо их там держать — все.

держать надо только итоговые. или, пока процесс идет — кандидатов в итоговые.

я вот на пыхе побаловался
674.6 Mbyte; 2 388 267
Time: 163s
pastebin.com/E6PfAehb

диплом гавно, алгоритмы гавно, а надо знать только фреймворки ©

EasyMorph в помощь (под win, trial версии под вашу задачу хватит) — реестры фопов им парсил, и потом можно легко в любую бд или тот же csv закинуть

Програмістичний топік на ДОУ? Hell has frozen over.

Импортируешь в mysql и спрашиваешь у неё потом всё что хочешь. Именно так это проще всего решить если цель получить данные. А вот если это какое-то хитрое тестовое задание — то тогда хз, это надо думать долго.

Ну а если вообще подсказывать то: dev.mysql.com/...​man/5.7/en/load-data.html

PowerBI вам в помощь. 10 минут на установку, минут 5-10 на загрузку файла и 5 на решение самой (или подобной) задачи.

тогда уж лучше QlikView. Есть бесплатная версия, под Windows. Правда — надо освоить Visual Basic :)

Visual Basic

точнее VBScript или JScript
но хрен редьки не слаще))

PowerBI бесплатный по-умолчанию. У меня есть опыт работы и с одним и с другим, и я считаю, что PowerBi уже превосходит Qlik практически во всем; да их даже сравнивать тяжело. Но даже, если не выбирать между этими инструментами для решения этой задачи программировать не придется, все можно реализовать слайсерами.

таки легче всего поднять какой то сиквел и в него все скинуть. у тебя дорогие операции с листами в питоне — они много времени занимают

Spark вам в руки
если лень — ниже рекомендовали как готовить pandas

да , спарк как раз штука для миллионных файлов, но можна попробовать и просто в питоне нафигачить скрипт только памяти побольше

В суть не вникал, но у меня при решении подобных задач, обычно после остается папка temp c 4 Гб файлов типа 4f944cd9-f98b-481d-a3c5-96086230a522.json . Это если надо по быстрому.

Ради тупого примитива в 400мб? Мда...

Ради тупого примитива в 400мб?

Не имею понятия сколько там мегабайт. И вообще я задачу не читал. Если надо что-то сделать побыстрому с большими обьемами в памяти не заморачиваясь — всегда все промежуточные вычисления сбрасываю на диск.

Ну, операция сброса на диск — это уже заморочка. Надо создавать свой способ хранения, или брать что-то существующее, а потом парсить, и эти операции часто далеки от оптимальных (они твоих задач не понимают).

Потому правильное решение — индексировать существующий файл, просто запомнив метки участков с которыми предстоит работать. И безо всяких промежуточных сбросов работать напрямую с файлами, тем более что операционка как правило файлы кеширует, когда имеет под это неиспользуемую память. Итого — и скорость, и скорость, и памяти мизер захватываешь.

А если по-хорошему, то при перегоне в свой формат (это полезно, когда задача не одноразовая) проще взять базу данных, которая штатными средствами всё счастье разложит по полочкам и проиндексирует. Тот же самый SQLite справится ничтоже сумняшеся.

Коментар порушує правила спільноти і видалений модераторами.

Предлагаю использовать R

Ссылку на датасет с подменными данными (если важно) в студию. Ответы про базу правильные, но если задача — обойтись без базы совсем, мне было бы интересно на сете опробовать это

Скільки в файлі різних артикулів, виробників і товарів? Скільки є типу значень для фільтрації: типу два виробника і до десяти артикулів чи ця кількість може бути довільною? Яка є кардинальність множини даних після фільтрації (приблизно), тобто скільки рядків буде після фільтрації вхідного набору даних по критеріям виробника і артикулу? В залежності від цього можна обирати той чи інший варіант рішення, тобто створюючи якісь допоміжні індекси чи без цього. Це такі задачі зараз в університеті задають?)

Ще один варіант — використати MS Access. Там усе можна зробити максимально спрощено (з візуальним інтерфейсом), та й об’єм у 6 млн. рядків для нього не проблема.

mysql поддерживает операцию импорта цсв файла

Никогда не пробовал, но вероятно придётся руками скармливать настройки сепаратора.
Таки как и предполагал, согласно RTFM надо вручную в команде указать сепараторы строк и столбцов, а ещё поля принимающей таблицы заведомо должны быть в точности те, которые в CSV, и в том же порядке созданы.

Но как по мне, это — решение, и нефиг городить другие. Дёшево, сердито, многоразово и никаких тебе заморочек рулить этим счастьем удалённо, вплоть до кронтаба.

надо вручную в команде указать сепараторы строк и столбцов

вот это совсем не проблема

принимающей таблицы заведомо должны быть в точности те, которые в CSV, и в том же порядке созданы.

так у него же известный датасет

а вообще есть mysql workbench с UI и туториалом для совсем ленивых dev.mysql.com/...​-export-import-table.html надо только мышкой поклацать

Навскидку такой алгоритм:
1) Открываем исходный файл, читаем построчно.
2) Для каждой строки считаем хэш ключа группировки и цену.
3) Ищем хэш в словаре вида: хэш = ключ, цена, номер строки.
4) Если не нашли — то пишем строку в файл результата и заносим в словарь смещение строки от начала файла.
5) Если нашли и цена в словаре меньше — пропускаем строку.
6) Если нашли и цена в словаре больше — пишем строку в файл результата и апдейтим в словаре цену и номер строки.
7) Когда прошли весь исходный файл — имеем заполненный словарь в памяти и файл результата (с дупликатами).
8) Из словаря копируем номера строк в отсортированный массив. Словарь больше не нужен.
8) Открываем файл результата и копируем из него в финальный файл только те строки, которые есть в массиве. Для этого идем по массиву и сикаем файл стрим на нужное число.

8 неоптимально. Операция чтения последовательно намного дешевле seek. потому оптимально читать файли и переписывать в другой если номер строки есть в памяти.

В базу даних завантажити же ж.

В условии про субд ни слова. Имхо нужно открыть файл потоком и пройтись по нему 1 раз. В ходе прохода определить минимальную цену товара и сразу писать в выходной поток строки исключая все строки с нашим товаром. В самом конце добавить 1 запись с товаром минимальной цены (порядок строк скорее не важен). При этом в RAM грузим максимум 2 строки. Скорость зависит лишь от вашего диска. Если писать и читать с разных hdd скорость будет хорошая. Или ssd :)

В самом низу Леголас это же (плюс-минус) написал позавчера. Почему ТС после этого продолжает изобретать велосипед — тайна великая есть...

Ну он там словарь еще добавлял. Как по мне это лишнее. Хранить можно только 1 запись нашего товара с минимальной ценой.

У нас не одна минимальная цена, а столько, сколько уникальных пар (производитель, артикул) имеется в исходном файле.

Перечитал условие. Таки да. Задача сложнее чем показалась вначале. Тогда считываем все цены в словарь оставляя минимальные. И только потом сохраняем.

Не знаю про пітон, а зазвичай робив так.

— три масиви, два індeксних, трeтій для рeзультату.
— читаю рядок. Шукаю код для артикула і виробника. Як нeма, додаю іх до відповідних індeксів.
— формую код для рeзультату. Наприклад кодАртикула << 15 | кодВиробника. Чи навпаки, залeжить від кількості унікальних артикулів та виробників
— шукаю по ньому рeзультат. Порівнюю за потрібними критeріями. Збeрігаю, якщо більш гідний.
— в кінці маю рeзультат.
— індeксні масиви можна тeж збeрeгти, для іншого критeрія, або файла.

Звісно, якщо масиви в мові чeсні.
Як нeма в мові масивів, то використувавати або мапу, або дeрeво

На саму установку MS SQL утричі більше часу піде, ніж на виконання цієї роботи підручними інструментами, типу SQLite3.

Якщо задача реально бізнесова — запхай ото все щастя в Excel, відсортуй, накинь автофільтр та візьми із полиці пєчєньку. Теж мені, проблема сторіччя, 400Мб обробити.

Якщо питання лише в цьому — підіймай базу даних, заливай дані в неї. Excel на основі бази легко генерує зведену таблицю. Теоретично він може і CSV взяти через ODBC, я не пробував.

Excel — платный и с такими файлами (кол-во строк и размер) не очень удобно работать.

Якщо завдання не учбове, взяти базу, згодувати дані, отримати щастя. Навіщо вигадувати самокат із педалями?

Якщо завдання учбове — ти вже спалився коли запостив його на DOU.

PS. Насправді нема проблем згодувати ці 400Мб в оперативку та виконати завдання миттєво. Але че є під це завдання стільки оперативи? Якщо нема, то в тебе вихід лише індексувати файл.
Дивися що робиш:
1) В тебе на вході є критерії: артикул і виробник. Якщо ти передбачаєш що таких знайдених записів не мільйони, то просто складаєш в пам′ять виключно те що знайшов первинним пошуком. Але є але: якщо шукаєш не повним збігом, тобто за частиною строки чи навіть можлива порожня — на виході матимеш монстра у пам′яті.
2) Серед знайденого не робиш ніякого сортування. Просто пробігаєш все, обираєш меншу ціну. Потім знову пробігаєш все, і пишеш в CSV виключно те, де різниця в ціні не більша за 10 коп. Чому так:
— завжди є несуттєва різниця, вона не має впливати на результат. Якщо хтось поставив ціну 99.99, ти не повинен втратити результат 100.
— є похибка перетворювання дробу. Тобто, 1.3 може перетворитися в 1.2999999999995, і ти втратиш результат.

Чому не трахаєся із сортуванням чи оптимізацією:
— операції в пам′яті дуже швидкі.
— операція читання змінної значно швидша за операцію створення об′єкту.
— працювати лінійним алгоритмом значно простіше, ймовірність помилки найменша, а перевірити такий алгоритм значно легше.
— не створюється сміття в пам′яті.

Так працюють високонавантажені алгоритми в реальних задачах. Все інше — марення тєорєтіків.

Dear Sir, I can do this manually for you in a week. Our team consists of great developers. We are new on this website. If you award us we don’t rest until the job done.

Годно!

Перегони его в базу, выполни запрос.

Спробував імпортувати в SQLite і десь через 20 хвилин очікування відкринув цю ідею.

кодом пахнет :) обрабатывать 20 мб в минуту... и даже не 20, а то бы завершилось...

може ви робили все вірно і то sqllite тупить, але найпоширеніша помилка імпорту цe — прочитав однeньку позицію — записав у sql.

А треба
— таблиця без індeксів. Як вони є — дропнути іх.
— читаємо і формуємо sql скріпт. На 1 мб мінімум. Один вeликій insert в ньому.
— відправляємо його в бд.
— читаємо далі, формуємо, відправляємо.
— після повного імпорту повертаємо- додаємо індeкси

Ви щось десь не те зробили, припускаю, що заганяли це не із командного рядка (тобто не на пряму утилітою sqlite3).

Я заганяю 100 тис. за три секунди. Тобто ваші 6 млн. мабуть би залитіли у базу SQLite десь до 5 хв., максимум (навіть якщо у вашому файлів довші рядки і більше стовпців).

Я пишу команди для SQLite у звичайний текстовий файл з розширенням .sql, а потім виконую їх через:
sqlite3 < /path/to/your.sql

Так. Знайшов якусь програму з GUI і з її допомогою пробував імпортувати в БД.

У большинства баз есть специальные инструменты для батчевой загрузки. Например dev.mysql.com/...​man/5.7/en/load-data.html

6 миллионов записей для неё это вообще не проблема

приколи — короче берешь такой делишь на батчи и работаешь
Оо
А если Вам сударь нужен поиск по бинарному дереву в csv файле, то Вы наверное просто смузи вчерашнего выпили — отдохните недельку и все пройдет :)

Поиграй с сетами, память это не проблема (800Мб это ничто). Можно конечно и спарки и хадупы и еще чего навернуть, но проще — в момент чтения создай дополнительные сеты для каждого производителя и + одни сов всеми артиклулами, а потом делай их пересечение. В коде что вверху, проблема скорее всего где-то здесь (с первого взгляда) :

matches = set(number_list).intersection(number_array)

Перевод листа в сет это не дешевое удовольствием
Так же , посмотри внимательно что именно возвращает .items() очень даже может быть что list, это не хорошо, если те обекты это dicts , делай просто for i in dict:
В общем , обычно все парсится за 10-20 секунд (по крайней мере на размерах в околе 1-2 млн CSV линий) , если быть аккуратным

UDP. вот то что Леголас говорит звучит хорошо, если это можно сделать в рамках задачи

Перевод листа в сет это не дешевое удовольствием

Дрочерам на LINQ в C# посвящается, как говорится.

Можно конечно и спарки и хадупы и еще чего навернуть, но проще

ORLY? Простіше, ніж 3 рядки коду для Spark?

val data = sc.textFile("file:///home/bj/input.csv")
val cheapest = data.
  map{row => { val cells = row.split(","); ((cells(0), cells(1)), (cells(2), cells.drop(3).mkString(","))) }}.
  reduceByKey{case ((price1, tail1), (price2, tail2)) => if (price1 < price2) (price1, tail1) else (price2, tail2)}.
  map{ case (x, y) => x.productIterator.mkString(",") + "," + y.productIterator.mkString(",")}.
  coalesce(1)
cheapest.saveAsTextFile("file:///home/bj/output")
Article1,Brand1,101,data11,data12
Article1,Brand1,102,data21,data22
Article2,Brand1,103,data31,data32
Article1,Brand2,104,data41,data42
перетворюється на
Article1,Brand1,101,data11,data12
Article2,Brand1,103,data31,data32
Article1,Brand2,104,data41,data42

Номер карточки Приватбанку для прийому подяки — 4731 1856 1011 3711 )))

А якщо серйозно, згадалася співбесіда, на яку недавно запрошували з одного крупного львівського аутсорсера. Спитали, якими інструментами вирішував би задачку, схожу на цю. Я: «Scala+Spark». Бо реалізація пишеться швидко, виглядає елегантною і читабельною, (на великих данних) швидкодія виходить хорошою і Spark сам попіклується про оптимальність байткоду. Технічні експерти здивувалися, чому не стандартні засоби java, адже ними теж можна організувати багатопотоковість — я додати не мав що )))
Коротше, чим з більшою кількістю мов програмування, бібліотек, інструментів працював, тим кращі рішення для розв’язання задач можна знаходити.

Реально ? Т.е. для того что бы распарсить цсв файлик на лаптопе мне нужно поставить спарк? или как еще народ рекомендовал — бд. Эта задачка делается в консоле питона за пару минут и парсинг занимает 10-20 секунд, но да, давайте сейчас развернем ферму на 20 серверов.
Если у вас каждую минуту приходит такой файлик который нужно парсить и потом что-то куда-то сохранять, то да — без вопросов, если это один файлик который нужно распарсить один раз (что весьма похоже из описания задачи) , то да, нечего добавить :)

Спарк ставиться так:
1) скачати;
2) розархівувати.
Так, є задачі, для яких його треба конфігувати, розгортати на кластері. У даному випадку можна обійтися без цього.

Якщо ця задачка вирішується за пару хвилин, чому б тобі не запостити код, який буде обробляти файлик за 10-20 секунд? ;)

Я займався тюнингом speed performance та memory usage, і знаю, що аби написати те, що ти пропонуєш, треба врахувати багато речей:
1) неконтрольоване скидання даних у файл підкачки, якщо забато підчитується в оперативку (дані, що на диску займають 400 MB, в оперативці можуть займати в рази більше);
2) складність алгоритму (автор запропонував O(n_brands * n_articles * ...), що вже неправильно, якщо категорій багато);
3) часті перетворення tuple->set (що неправильно, якщо кількість елементів у категоріях велика) — ти це підмітив;
4) можливо, ще якісь завтики, які так зразу не кидаються в очі.

Spark дозволяє програмісту (у даній задачі) зовсім не думати про ці всі нюанси, а бере на себе генерацію оптимального коду. :)

Иван, всё говорите верно, за исколючением оного: неверно овладевать Spark при отсутствии алгоритмической базы. А то потом рождаются сначала ужасные решения, а потом не менее ужасные статьи на тему «почему Spark-говно».

Конечно руки чешутся порекомендовать автору Java streams, или проще — Scala streams — но опять-таки, человек хочет сделать быстро и просто, а не осваивать матчасть.

Можливо, Ви праві...

Хочеться вірити, що навіть якщо топікстартер і скористається (з метою встигнути до дедлайну?) Spark-ом (чи іншим інструментом, що сам знаходить оптимальний алгоритм), то потім з’ясує, чому вручну написаний алгоритм працював довго.

попробуй spark dataframe, у него есть и питоновский API

Для Python есть Pandas. Отлично помогает крутить данные, делать sort, group by, join, merge строить графики и прочее. Причем делает это в памяти намного приятнее и гибче базы данных. Читает разные форматы данных, в том числе и csv. При небольшом количестве колоном весь ваш csv на 6 млн записей легко поместитьсяв память на 8Gb. Если данные не влезут в память целиком, то их можно считывать батчем или загружать в память только нужные вам колонки

Даском я отлично параллелил обработку данных, т.к веселый Python однопроцессный и крутить 12Gb куски видя, как одно ядро загружено на 100%, а остальные простаивают — это удовольствие не для слабонервных. С его помощью и добавления хеша по составному ключу удалось оптимизировать скорость выполнения кода с одной недели до 1.5 часов на 12Gb данных. И заводить Spark не пришлось :)

Какой-то вы сложный путь выбрали кмк.
grep -E 'vendor1|vendor2|vendorN' file.csv | grep -E 'article1|article2|articleN' | sort -t',' -n -kNUM,NUM | head -X
Где «NUM» — порядковый номер колонки с ценой, а «X» — сколько минимальных цен выбрать.

На большом файле sort пожрет порядочно памяти разве что. Но это только концепт — на питоне можно использовать более эффективную сортировку.

Самый элегантный способ зашифровать rm -rf

Да ладно — это самый простой вариант чисто для наглядности что за чем делать.
Ни sed ни awk не используется же. )

Кстати — любой админ 90х-начала 2000х пишет такие парсеры на лету даже не задумываясь по 5 раз в день, когда нужно информацию из логов добыть. К вопросу о 60-летних программерах ;)

Ни sed ни awk не используется же. )

В этом и беда, потенциальные баги прям на поверхности, а вот авк команда теряет понятность даже для автора минут через 15.

Желательно запускать rm -rf с sudo и на корневой директории.

Дякую за лінупсову магію, але потрібно зробити без неї.

Вот же молодежь )
Ладно, еще проще:
1. Выбираем из файла в массив все строки, где есть нужные нам производители
2. Выбираем из получившегося массива в новый все строки, где есть нужные нам артикулы
3. Последний массив сортируем по увеличению цены
4. Выбрасываем в результат первые Х строк отсортированного массива

В данном алгоритме единственная относительно «тяжелая» функция — сортировка на 3 этапе, но т.к. к этому моменту мы уже имеем небольшой массив, она пройдет быстро.

Ради инетереса попробовал с грепом и файлом который предоставил топикстартер, на ссд можно не индексировать вышло 0.2 секунды. Проц: i5-3230M Винт: Samsung SSD 850 EVO 500GB

О чем и речь. Но топик уже погряз в бигдате и ИИ, их уже не остановить...

Ради инетереса попробовал с грепом и файлом который предоставил топикстартер, на ссд можно не индексировать вышло 0.2 секунды.
Ага, греп таки таки быстр. Осталось только понять при чем он к решению описанной ТС задачи :)

Через grep/sed/парсинг полей строится система pipes and filters, которая в результате прогона входных данных на выходе дает результат. Смотри, например, комент, на который отвечаешь.

Ты видишь что-то про `sed` в комменте, на который я отвечал? «- Ты суслика видишь? — Нет. — И я нет... а он есть»

И второй вопрос: ты правда думаешь, что если запилить все пайпами с седом, то на 6 миллионах строк описанная задача будет решена за 0.2 секунды?

и какой у вас вышел результат?
т.е. какой размер файла?

Я сейчас не делал. Судя по команде, на выходе 1 строчка.

Вот меня и удивила скорость работы. Копирнуть в /dev/null думаю еще быстрее

4 года назад на среднем компе без SSD 10ГБ файл обрабатывался sed или С++ 3 минуты. grep должен давать подобную скорость. Но железо поменялось с тех пор.

Я не понимаю что такое — обрабатывался.

обрабатывался — значит, был файл формата id, a, b, c, int1, int2; одна запись в строке. Искали id для минимального и максимального значения полей int1 и int2. Поспорили про скорость питона, С++ и линуксовых утилит, и решили проверить.

ну питон то понятно что тормоз.

просто в этой задачи нет id.
его нужно формировать в каком-либо виде по a и b.

ну, и если брать тупо пропорцию, размер-время
10Гб — 3 минут
400Мб — получается что обработает за 7 сек

0.2 секунды как-то все равно фантастично смотрятся :)

хотя, если мемори дб, да колоночная, то вполне может.

может на джаве набросаю, в двух вариантах, одно и двух поточном.
но, если скажем в 10 раз лучше пыха, то выйдет — 16,3s

А вот и не тормоз. Всего в 3 раза медленнее, чем С++ или линуховые утилиты.

Всего в 3 раза

ну это да, вот если бы в 30 раз, то это тормоз.
а в 3 раза — не тормоз :)

тут народ за проценты радуется прироста быстродействия радуется, а вы какой роскошный :)

За проценты — написать на плюсах, отпрофайлить, оптимизнуть, и еще раз отпрофайлить. Для остального ± в 3 раза это очень даже хорошо.

это все понятно.
я потому и на пыхе сделал, а на джаве — нет :)

да и не только я. даже тяжелых сайтов на пыхе много больше чем на джаве :)

Ага, греп таки таки быстр. Осталось только понять при чем он к решению описанной ТС задачи :)

Ему надо выбрать по двум полям, из его данных я не знаю как получить большую выборку по фильтрам, чтоб ее сортировка занимала хоть сколько то заметное время.
Это я больше к тому, что современному процессору перелопатить этот объем данных плевое дело все упрется в скорость чтения с диска, других тяжелых операций кроме фильтрации записей в задаче не вижу.

Ему надо выбрать по двум полям
Ему нужно не выбрать по двум полям (с чем таки прекрасно справится греп), а убрать дубликаты артикулов (точнее, пары [производитель, артикул]), оставив только строки с минимальной ценой.

Ну тогда через хеширование пары, и в мапу их. В задании написано, что надо сделать поиск по паре значений, а не что надо очистить файл от неоптимальных цен.

Потім серед груп товарів які мають однаковий артикул і виробника знайти товар з найменшою ціною а всі інші з цього набору однакових товарів видалити

OMG WTF «Фулл стак сень’р веб девелопер»

1. Перегнати CSV в будь-яку реляційну БД (e.g. sqlite), відіндексувати за двома полями, вибрати результат, перегнати в CSV.

2. Те ж саме, руками. Проіндексувати дані за О(n), одразу вибиваючи більшу ціну з індекса. Вибрати результати з індекса. Це має працювати в межах 2x просто парсингу CSV.

idx = { }

for row in CSV:
	if not match_criteria(row):
		continue
	key = "%s-%s" % (row.article, row.mfgr)
	if key in idx:
		old = idx[key]
		if old.price < row.price:
			continue
	idx[key] = row

for row in idx:
	print_csv(row)

OMG WTF «Фулл стак сень’р веб девелопер»

Стьоб.

Після збору даних даних ось що роблю: масив numbers кожного виробника порівняти з масивом numbers всіх артикулів і якщо перетин масивів містить більше одного елементу, додати цей масив номерів рядків до масиву з копіями.

І яка алгоритмічна складність того алгоритму?

Зроби просто 1 словник з предметів:
виробник => {
арт1 { <данні> },
арт2 { <данні> },
}
За один прохід по CSV зчитуєш той словник. Якщо тобі попадається товар якого нема в словнику то просто додаєш його туди, якщо попадається такий, який вже є — порівнюєш ціну і в своєму словнику зберігаш дешевший. Потім записуєш той словник в CSV.

Які ще блін інтерсекшени, ти шо?

І яка алгоритмічна складність того алгоритму?

Who knows.

Хороша ідея, але якщо зчитати ще й ціну, то воно «падає» з memory error.

Ну так модифицируй, чтобы все данные в память не тащить. В первый проход собери из исх. файла минималистичный словарь (например, вида { «manufacturer | item» => min_price } - т.е. склеив ключи из производителя/артикула), а вторым проходом читай построчно из исходного файла и тут же построчно пиши в результирующий, если цена соответствует цене из словаря...

6 млн. дійсно багато. pandas вже вище радили, може він считає ту справу еффективніше.

6млн это ерунда для современных компьютеров, даже если вы совсем дубово будете сортировать. Не плодите сущности. Много — это обьемом в 3-4 размера оперативки. А сейчас впс с 64Гб на час стоит 1доллар.

Ну не для любой же задачи ты бужешь брать этот ВПС, особенно если ты джуниор :) Все, что просто так не влазит в память влоб — много. Хотя я не совсем понимаю как 6 млн записей не влезло в оперативку.

Хотя я не совсем понимаю как 6 млн записей не влезло в оперативку.

Реализация подкачала :) Я проверил ради интереса — примитивный скрипт на руби из пары десятков строк переколбасил по такому методу (в два прохода — сначала собираем словарь в памяти, потом построчно читаем и пишем отфильтрованное) словарик в 5.8 миллионов строк за 2.5 минуты примерно. Процесс распух до полутора гигов примерно, а это довольно далеко до «не влезло в оперативку». У ТС справочник побольше, но не настолько, чтобы прямо космически цифры отличались...

Підписатись на коментарі