Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: 1 2 3 4 5      [все]
 Работа с большими данными  [new]
Андрей Александрович.
Member

Откуда:
Сообщений: 44
Приветствую

Подскажите решение следующей задачи

Есть текстовые данные - порядка 2 тб в виде набора файлов ( файлы от 200 мб до 150 гб )
Задача проверить все файлы и удалить дубликаты ( а так же скомпоновать данные )

Правильным ли решением будет использовать для этого СУБД ?
т.e

1 - читаем файл с данными построчно
2 - вносим данные в БД
3 - перед внесением данных проверяем есть ли уже такая запись в БД

Отсюда вопросы

- как лучше проверять уникальность ? SELECT ? LIKE ? хранимой процедурой ? триггером на INSERT ?
- Какую БД лучше всего использовать ? Есть опыт работы с MySQL, MSSQL, SQLite, Firebird
- Есть ли готовые решения для поиска дубликатов в таких обьемах данных ?
19 авг 17, 23:25    [20736437]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Андрей Александрович.
Member

Откуда:
Сообщений: 44
> и удалить дубликаты

Дубликаты данных которые находятся в файлах
19 авг 17, 23:26    [20736445]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
Андрей Александрович., успех этого мероприятия зависит от ваших ресурсов.
Самый прямой и надежный вариант - загрузить используя всякие базёвые
утилиты *loader-s ваши данные в одну табличку. И delete-ом почистить
дубликаты. В запросе использовать аналитические функции (PARTITION BY).
19 авг 17, 23:44    [20736463]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mikron
Member

Откуда: Germany / Stuttgart
Сообщений: 764
Андрей Александрович.
2 тб в виде набора файлов ( файлы от 200 мб до 150 гб

Это реально много.
Андрей Александрович.
Правильным ли решением будет использовать для этого СУБД ?

Скорее нет чем да. И скорее всего все другие вопросы не релевантны.
Андрей Александрович.
- Есть ли готовые решения для поиска дубликатов в таких обьемах данных ?

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

Для создания списков уникальных значений потребуется на скромный взгляд ещё 2 - 3 ТБ.
И считатся это будет наверно дни. на вскидку и без базы данных. Такая работа стоит времени специалиста и за пределами бесплатных консультаций. ИМХО.
20 авг 17, 01:26    [20736547]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 6104
mikron,

хэширование спасет мир
20 авг 17, 01:33    [20736552]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
982183
Member

Откуда: VL
Сообщений: 2719
1. Речь идет о текстовой неструктурированной информации, или о реляционных данных, хранящихся в текстовом виде?
во втором случае каково количество полей данных?
2. Чем вызван такой способ хранения данных?
2. Чем отличаются отдельные файлы. (Это последовательно обрезанный поток данных, или это данные с разных источников?)
20 авг 17, 05:51    [20736590]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
ВМоисеев
Member

Откуда: Редкино
Сообщений: 1818
>Андрей Александрович., вчера, 23:25 [20736437]

>...Правильным ли решением будет использовать для этого СУБД ? ...
Рассмотрите такой вариант:
1. Все текстовые файлы находятся в папке файлового сервера - смысловая часть.
2. Поисковая часть (суррогатный_ключ, пользовательское_имя_файла, группа, когда_создан и т.п) находится в записях таблицы(ц) базы данных.
3. Файлы смысловой части имеют имена производные от суррогатного ключа.

С уважением,
Владимир.
20 авг 17, 08:30    [20736613]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Андрей Александрович.
Member

Откуда:
Сообщений: 44
982183
1. Речь идет о текстовой неструктурированной информации, или о реляционных данных, хранящихся в текстовом виде?
во втором случае каково количество полей данных?


Файлы представляют собой хранилища слов всех языков мира
те списки слов на разных языках

982183
2. Чем вызван такой способ хранения данных?


Дали файлы - сказали решить вопрос с дубликатами и хранением

982183
2. Чем отличаются отдельные файлы. (Это последовательно обрезанный поток данных, или это данные с разных источников?)


Это файлы с разных источников ( часто даже с различным способом хранения данных - те нужно будет к каждому файлу писать парсер или свою проверку корректности данных. Учитывая что там еще слова на разных языках то переводить все в UNICODE )
20 авг 17, 08:55    [20736626]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Андрей Александрович.
Member

Откуда:
Сообщений: 44
mikron
Возможно есть в биоинформатике. Но ваша задача, если я правильно предпологаю, не поиск одного дупликата и не поиск всех дупликатов.


Задача - очистка данных от повторяющихся слов
А так же упорядочивание данных при возможности

mikron
Для создания списков уникальных значений потребуется на скромный взгляд ещё 2 - 3 ТБ.
И считатся это будет наверно дни. на вскидку и без базы данных. Такая работа стоит времени специалиста и за пределами бесплатных консультаций. ИМХО.


Есть свободные 3 тб те куда делать временные таблицы есть
По времени если пересчет займет 3-9 дней - не проблема. Вопрос именно в том как наиболее быстро сделать чтобы поиск добавление в БД не заняло например месяц или больше

Я так подозреваю что после решение этой задачи станет обработка данных
А лучше всего это делать если данные будут упорядоченны например в БД
20 авг 17, 08:58    [20736633]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
982183
Member

Откуда: VL
Сообщений: 2719
Андрей Александрович.
Файлы представляют собой хранилища слов всех языков мира
те списки слов на разных языках

Т.е. намечается два поля - "Язык" (который берем из файла) и "Cлово"

982183
Дали файлы - сказали решить вопрос с дубликатами и хранением

Наверно с хранением и дубликатами.

982183
Это файлы с разных источников ( часто даже с различным способом хранения данных - те нужно будет к каждому файлу писать парсер или свою проверку корректности данных. Учитывая что там еще слова на разных языках то переводить все в UNICODE )

Так эта задача однако на порядок сложнее, чем организовать хранение и чистку.
20 авг 17, 09:06    [20736645]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
982183
Member

Откуда: VL
Сообщений: 2719
Почему на этом гр*** форуме нельзя редактировать посты....
Обычную описку исправить нельзя.
20 авг 17, 09:07    [20736646]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
Из коробочных решенийй.

Можно посмотреть на unix-утилиты такие как:
1) sort -u
2) unique

и посмотреть их настройки в части использования $tmp как пространства для сортировок.

Если эти коробочные штуки "не взлетят" то можно попробовать грузить в БД. Но грузить
надо грамотно. Учитывая объем - желательно использовать утилиты для bulk/batch загрузки.
Но дальше об этом говорить безсмысленно. Автор должен сообщить нам какая именно
dbms у него выбрана и дальше уже можно что-то советовать более конкретно.
20 авг 17, 09:08    [20736647]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
982183
Member

Откуда: VL
Сообщений: 2719
А что делать с омонимами?
20 авг 17, 09:10    [20736651]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Андрей Александрович.
Member

Откуда:
Сообщений: 44
mayton
Из коробочных решенийй.

Можно посмотреть на unix-утилиты такие как:
1) sort -u
2) unique

и посмотреть их настройки в части использования $tmp как пространства для сортировок.



Спасибо
Изучу

mayton
Если эти коробочные штуки "не взлетят" то можно попробовать грузить в БД. Но грузить
надо грамотно. Учитывая объем - желательно использовать утилиты для bulk/batch загрузки.
Но дальше об этом говорить безсмысленно. Автор должен сообщить нам какая именно
dbms у него выбрана и дальше уже можно что-то советовать более конкретно.


Вот это был один из вопросов
Есть опыт работы с СУБД

MySQL, MSSQL, SQLite, Firebird
Какую посоветуете для хранения больших данных ? ( к сожалению с Oracle не работал )
20 авг 17, 09:13    [20736655]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
Андрей Александрович.
Вот это был один из вопросов
Есть опыт работы с СУБД

MySQL, MSSQL, SQLite, Firebird
Какую посоветуете для хранения больших данных ? ( к сожалению с Oracle не работал )


По этим СУБД я не специалист. Я больше по Oracle.

Немного работал с MSSQL. И конечно исходя
из авторитета самого вендора я порекомендую MSSQL. Кроме того есть
мысль что аналитические (оконные) функции там поддерживаются.

По поводу SQLite - есть сомнения. Она очень производительная но работает
в условиях когда data segment помещается в оперативку. Если вам удастся
ваш самый крупный справочник прогрузить в SQLite - тогда все будет ОК.
Но и с PARTITION BY надо тоже проверить.

По поводу остальных. Велкам в Сравнение. Задавайте вопросы там. Думаю что помогут.
https://www.sql.ru/forum/db-comparison
20 авг 17, 09:24    [20736668]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
schi
Member

Откуда: Москва
Сообщений: 2601
По-моему можно вызять любую СУБД и организовать в ней таблицу с одним полем и уникальным индексом по нему. Далее последовательно читать все файлы и каждое слово пытаться записать в эту таблицу. Если не удалось, то значит дубль, если удалось, то записывать слово в выходной файл.

(Насколько я понял задачу).
20 авг 17, 10:40    [20736710]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
982183
Member

Откуда: VL
Сообщений: 2719
Т.Е отсечь дублирование на этапе импорта данных....
мысль хорошая.
20 авг 17, 11:08    [20736731]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
skyANA
Member

Откуда: Зеленоград
Сообщений: 26364
А я понял задачу так: например есть у нас три файла разного формата, в каждом из которых подмножество слов французского языка.
Нужно данные каждого файла распарсить, нормализовать и залить в БД.

ИМХО - это простой импорт из различных источников.
Заливаем данные файла в промежуточную таблицу в схеме import, перегоняем в основную только те слова, которых там ещё нет (WHERE NOT EXISTS).
В основной таблице должен быть соответсвующий индекс.
20 авг 17, 11:08    [20736733]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
skyANA
Member

Откуда: Зеленоград
Сообщений: 26364
ИМХО большая часть времени уйдёт на написание партеров-загрузчиков из различных форматов.
20 авг 17, 11:11    [20736736]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
Чисто в качестве brainstorm ... можно попробовать зарегаться в Amazon AWS.
И там будут доступны всякие API и хранилища для толстых данных.

Попробовать прогрузить туда табличку в 150Гиг и там отфильтровать.

Возможно но этом шаге Amazon попросит оплатить услугу а может и нет.
Вобщем я-б попробовал. Или взять табличку в два раза меньше и еще раз
попробовать.
20 авг 17, 11:11    [20736737]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
skyANA
Member

Откуда: Зеленоград
Сообщений: 26364
Андрей Александрович.,

а вообще как эти данные потом будут использоваться? А то можно и в MongoDB их засунуть с шардированием из коробки.
20 авг 17, 11:12    [20736738]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
Все слова одного языка вполне можно обработать в оперативной памяти.
20 авг 17, 11:12    [20736739]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
Aleksandr Sharahov, на чем будешь писать? Delphi? C#?
20 авг 17, 11:49    [20736768]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Андрей Александрович.
Member

Откуда:
Сообщений: 44
skyANA
Андрей Александрович.,

а вообще как эти данные потом будут использоваться? А то можно и в MongoDB их засунуть с шардированием из коробки.


По данным планируется поиск и выборка по 200 - 300 тыс записей
20 авг 17, 11:52    [20736772]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Андрей Александрович.
Member

Откуда:
Сообщений: 44
mayton
Aleksandr Sharahov, на чем будешь писать? Delphi? C#?


Возможно вопрос автору темы

Писать планирую на delphi
20 авг 17, 11:52    [20736775]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Андрей Александрович.
Member

Откуда:
Сообщений: 44
skyANA
ИМХО - это простой импорт из различных источников.
Заливаем данные файла в промежуточную таблицу в схеме import, перегоняем в основную только те слова, которых там ещё нет (WHERE NOT EXISTS).
В основной таблице должен быть соответсвующий индекс.


Вот тут то и вопрос - как делать правильно ? Для каждого слова делать отдельный запрос в БД ?
Или можно как то триггером это обработать при вставке ?
20 авг 17, 11:54    [20736777]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
Андрей Александрович.
mayton
Aleksandr Sharahov, на чем будешь писать? Delphi? C#?


Возможно вопрос автору темы

Писать планирую на delphi

Да. Все верно. Я как раз автора хотел спросить.
20 авг 17, 11:59    [20736786]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
Вот тут пишут как при вставке в MS-SQL игнорить ошибки уникальности

https://stackoverflow.com/questions/1139050/how-to-ignore-duplicate-key-error-in-t-sql-sql-server

можно взять за образец. Но поскольку речь идет о большом объеме вставок
я-бы еще почитал как делать тонкую настройку индекса (таблицы?) в MS-SQL
для mass-inserts и еще надо-бы проверить режимы транзакций. Хорошо-бы
это делать одной большой транзакцией чтоб не было накладных расходов
на всякие-там open-close ...e.t.c. Впрочем я тут не спец. Возможно для MS
это не проблема.
20 авг 17, 12:07    [20736794]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6347
Андрей Александрович.
По данным планируется поиск и выборка по 200 - 300 тыс записей

Нет никакого смысла связываться с СУБД при таком количестве уникальных данных.
Используйте просто хеш-таблицу в памяти. Это будет самый быстрый вариант.
20 авг 17, 12:15    [20736806]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
Андрей Александрович.
Возможно вопрос автору темы

Писать планирую на delphi


Ну тогда хеш-таблицы будет достаточно http://guildalfa.ru/alsha/node/32
20 авг 17, 12:25    [20736814]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Андрей Александрович.
Member

Откуда:
Сообщений: 44
Всем спасибо
буду изучать предложенные варианты
20 авг 17, 12:32    [20736821]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
skyANA
Member

Откуда: Зеленоград
Сообщений: 26364
Андрей Александрович.
skyANA
ИМХО - это простой импорт из различных источников.
Заливаем данные файла в промежуточную таблицу в схеме import, перегоняем в основную только те слова, которых там ещё нет (WHERE NOT EXISTS).
В основной таблице должен быть соответсвующий индекс.


Вот тут то и вопрос - как делать правильно ? Для каждого слова делать отдельный запрос в БД ?
Или можно как то триггером это обработать при вставке ?

Не надо никаких отдельных запросов и триггеров.
Вставляете данные из файла в промежуточную таблицу как есть, а из неё уже одним запросом перегоняете в основную с условием WHERE NOT EXISTS.
После этого промежуточную таблицу очищаете.
20 авг 17, 13:05    [20736851]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Андрей Александрович.
Member

Откуда:
Сообщений: 44
skyANA
Андрей Александрович.
пропущено...


Вот тут то и вопрос - как делать правильно ? Для каждого слова делать отдельный запрос в БД ?
Или можно как то триггером это обработать при вставке ?

Не надо никаких отдельных запросов и триггеров.
Вставляете данные из файла в промежуточную таблицу как есть, а из неё уже одним запросом перегоняете в основную с условием WHERE NOT EXISTS.
После этого промежуточную таблицу очищаете.


Спасибо
20 авг 17, 13:11    [20736855]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 47259
Андрей Александрович.
буду изучать предложенные варианты

Если файлы текстовые с одним словом на строку, то, вероятнее всего, uniq отработает быстрее, чем вы напишете свой велосипед.
20 авг 17, 13:58    [20736901]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
Dimitry Sibiryakov
Андрей Александрович.
буду изучать предложенные варианты

Если файлы текстовые с одним словом на строку, то, вероятнее всего, uniq отработает быстрее, чем вы напишете свой велосипед.

Как быть с его толстым файлом который в 150Г ?
20 авг 17, 14:28    [20736926]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
skyANA
Member

Откуда: Зеленоград
Сообщений: 26364
Dimitry Sibiryakov
Андрей Александрович.
буду изучать предложенные варианты

Если файлы текстовые с одним словом на строку, то, вероятнее всего, uniq отработает быстрее, чем вы напишете свой велосипед.

Я так понял, что это не подходит, потому как повторяющиеся слова разбросаны по разным файлам.
А эти файлы в общем случае могут не одновременно загружаться. При этом ещё и иметь разный формат.
20 авг 17, 15:02    [20736958]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34421
mikron
Андрей Александрович.
2 тб в виде набора файлов ( файлы от 200 мб до 150 гб

Это реально много.
Андрей Александрович.
Правильным ли решением будет использовать для этого СУБД ?

Скорее нет чем да. И скорее всего все другие вопросы не релевантны.
Андрей Александрович.
- Есть ли готовые решения для поиска дубликатов в таких обьемах данных ?

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

Для создания списков уникальных значений потребуется на скромный взгляд ещё 2 - 3 ТБ.
И считатся это будет наверно дни. на вскидку и без базы данных. Такая работа стоит времени специалиста и за пределами бесплатных консультаций. ИМХО.


Да чё за бред-то? СУБД вполне адекватно могут это обрабатывать, там порядка 2 миллиародов записей (если по килобайту считать), не так и много. Т.е. много, но не запредельно много.

Берёте например Vertica или Virtuoso -- и оно вам всё всосёт.
Да, придётся повозиться с подготовкой данных, но это вполне ожидаемо.
20 авг 17, 15:18    [20736972]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34421
Андрей Александрович.
982183
1. Речь идет о текстовой неструктурированной информации, или о реляционных данных, хранящихся в текстовом виде?
во втором случае каково количество полей данных?


Файлы представляют собой хранилища слов всех языков мира
те списки слов на разных языках

982183
2. Чем вызван такой способ хранения данных?


Дали файлы - сказали решить вопрос с дубликатами и хранением

982183
2. Чем отличаются отдельные файлы. (Это последовательно обрезанный поток данных, или это данные с разных источников?)


Это файлы с разных источников ( часто даже с различным способом хранения данных - те нужно будет к каждому файлу писать парсер или свою проверку корректности данных. Учитывая что там еще слова на разных языках то переводить все в UNICODE )


Андрей, мне кажется, это задачка не совсем вам по зубам будет.
Ну всё же по уровню вопросов понятно, что опыта у вас маловато для такого.
Ну, там подсказывать и направлять можно долго, но делать-то всё равно вам.

У вас тут решающим будет вопрос о поддержке юникода в вашем приложении и в СУБД, имейте это в виду В ПЕРВУЮ ОЧЕРЕДЬ.
При чём это будет не просто какая-то поддержка юникода, а ПОЛНАЯ поддержка юникода.

Правда, может не всё так и плохо -- мы же так и не знаем, что там у вас за данные о словах, что там вам с ними надо будет делать, помимо удаления дубликатов (которое кстати также может быть весьма забавной задачкой, поскольку есть слова-омонимы, и вам нужно будет определять, это другое определение того же слова или это вообще другое слово-омоним).
20 авг 17, 15:27    [20736977]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
У меня есть подозрение что этих гигабайтных файлах полно всякого
шлака который надо не унифицировать а просто удалять. Сами подумайте.
Ни один писатель в мире больше сотни мегабайт текста не написал.

А здесь речь идет о гигабайтах. Что там за справочники? Что за словари?
Что там за данные? Это больше чем Британская энциклопедия.

Вобщем прошу автора прояснить.
20 авг 17, 15:39    [20736981]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mikron
Member

Откуда: Germany / Stuttgart
Сообщений: 764
Siemargl
mikron,

хэширование спасет мир

Не спасёт но делает его немного лутше.
После совпадения хеша надо делать полную проверку. Если сравнивать записи то будет много метаний.
20 авг 17, 16:21    [20737021]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
982183
Member

Откуда: VL
Сообщений: 2719
В однотомном словаре С.И. Ожегова представлены около 57 тысяч слов. В четырехтомном словаре, созданном под редакцией Д.Н. Ушакова, указаны более 85 тысяч слов. В семнадцатитомном словаре современного русского литературного языка, изданного Академией наук СССР, располагается 120 480 слов. В далевском «Толковом словаре живого великорусского языка» представолены более 200 тысяч слов!

Разные словари дают разную оценку словарному составу английского: некоторые источники насчитывают примерно 500 тысяч слов, другие - примерно 400 тысяч. Стоит остановиться на чем-то оптимальном - например, словаре Уэбстера, который насчитывает 425 тысяч слов. По некоторым подсчетам, активный словарный запас у самых начитанных европейцев и американцев насчитывает не более 20 тысяч слов, а пассивный - не более 100 тысяч.
20 авг 17, 16:26    [20737023]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
982183
Member

Откуда: VL
Сообщений: 2719
Другие источники говорят:
По версии GLM, сейчас английский язык насчитывает 1 миллион 4 910 слов. Причем согласно статистике, новое слово в английском языке появляется каждые 98 минут (в день 14,7 слов). А вот миллионный рубеж был преодолен 10 июня прошлого года в 10.22, когда эта компания зафиксировала еще одно новое слово Web 2.0, обозначающее новое поколение всемирной компьютерной сети.

http://www.languagemonitor.com/
20 авг 17, 16:28    [20737024]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mikron
Member

Откуда: Germany / Stuttgart
Сообщений: 764
MasterZiv
Да чё за бред-то? СУБД вполне адекватно могут это обрабатывать, там порядка 2 миллиародов записей (если по килобайту считать), не так и много. Т.е. много, но не запредельно много.

Я не говорил что ДБМС не справятся. Я сказал только скорее всего их применение не оправданна для этой задачи. С чем вы не согласны?
20 авг 17, 16:29    [20737025]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
mikron
MasterZiv
Да чё за бред-то? СУБД вполне адекватно могут это обрабатывать, там порядка 2 миллиародов записей (если по килобайту считать), не так и много. Т.е. много, но не запредельно много.

Я не говорил что ДБМС не справятся. Я сказал только скорее всего их применение не оправданна для этой задачи. С чем вы не согласны?

Мы сейчас обсуждаем алгоритм решения задачи не зная деталей. Может эта задача действительно
решается хеш-табличкой. Но нам нужен хоть какой-то estimation по поводу "толстого" файла.
Если там - низкая кардинальность то все 150 гиг свернутся в нормальные 200 тысяч слов английского
языка.
20 авг 17, 16:44    [20737042]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Bred eFeM
Member

Откуда:
Сообщений: 525
Андрей Александрович., хэширование память и сортировка спасет мир. Cерверок с 512ГБ уже купили/арендовали ?
20 авг 17, 16:47    [20737047]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mikron
Member

Откуда: Germany / Stuttgart
Сообщений: 764
mayton,

по моему больше высказывается догадок.
Задача же в постановке автора - есть 2тб данных, разбросанных по файлам. Логическая единица информации - запись, распологается одной строкой. Нужно удалить все дебликаты записей. Автор не спрашивает как ему организовать хранение этой информации для последующей обработки. Поэтому любая база - уже ненужные расходы. Кластеры, вертика, террадата и т.д. Все это можно но неоправданно.
Моя грубая оценка:
Любая база данных: доп расходы на хранение записей. Пусть 40 байт служебной информации на запись. При длинне записи в 60 байт мы получим в итоге 4 тб данных в базе. Всего 2^40 / 64 получим 16 милиардов записей.
Что бы убрать дупликатуы будем сортировать. Или есть другие предложения для базы?
Пусть будет сортировка. Значит нам потребуется ещё минимум 4 тб на временные таблицы.
Ну а про время я затрудняюсь даже оценить. Слишком большой разрос от дбмс.
Юниксовские утилиту уже лутше, но uniq работает на отсортированных данных. Ну а sort будет сортировать - во первых это не нужно, во вторых долго, в третьих потребует 4 тб
20 авг 17, 17:37    [20737086]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
mikron
Любая база данных: доп расходы на хранение записей. Пусть 40 байт служебной информации на запись. При длинне записи в 60 байт мы получим в итоге 4 тб данных в базе. Всего 2^40 / 64 получим 16 милиардов записей.
Что бы убрать дупликатуы будем сортировать. Или есть другие предложения для базы?
Пусть будет сортировка. Значит нам потребуется ещё минимум 4 тб на временные таблицы.
Ну а про время я затрудняюсь даже оценить. Слишком большой разрос от дбмс.
Юниксовские утилиту уже лутше, но uniq работает на отсортированных данных. Ну а sort будет сортировать - во первых это не нужно, во вторых долго, в третьих потребует 4 тб

Откуда вообще 60 байт? Вроде автор вообще не говорил ничего подобного.

И при чем здесь сортировка?
20 авг 17, 17:47    [20737095]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
mikron,

Слова разных языков, очевидно, различны.
В каждом языке ~ 10^6 слов.
Загрузка в хеш-таблицу одного языка ~ 0.1-1 мин.

Что потребуется дополнительно:
- дать файлам имена в соответственно языку,
- процедура чтения слов языка из файлов,
- процедура записи слов языка в файл.
20 авг 17, 17:59    [20737113]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mikron
Member

Откуда: Germany / Stuttgart
Сообщений: 764
Если же допустить что у нас 2^34 записей и мы можем адресовать запись одним 64bit словом то получится для хештаблицы потребуется 127 гб памяти.
При колизии хеша нужно проверять всю запись. А значит уже при 1% нужно будет проверить 256 милион записей. Hdd с при чтении в разброс с позиционированием головок при 16 мс получим 2^27 х 2^4 x 2^-10 x 2^-6 x 2^-6 получим 2 ^ 9 часов. После нахождения дупликата его надо удалить. Тут куча вариантов реализаций. Но 600 часов уже kill argument.
20 авг 17, 18:16    [20737131]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
mikron,

во-первых, записей никогда не будет больше, чем слов в одном языке,
во-вторых, они прекрасно лягут в хеш-таблицу в памяти.
20 авг 17, 18:25    [20737139]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
azsx
Member

Откуда:
Сообщений: 721
автор
Как быть с его толстым файлом который в 150Г ?

sort -u -T temp-directory file.txt > result.txt
Очень давно я чистил базы слов для сео (типа базы кеев пастухова в текстовых файлах, только сам собирал). Команда sort очень быстрая, по сравнению с моими реализациями и в несколько раз быстрее, чем реализации в БД. Для выборки кеев я в БД ваще только минусы вижу.
оффтопик
Как человек, который писал html поиск по главным нескольких десятков миллионов популярных доменов -- крайне рекомендую разобраться в своих кодировках. У азиатов и исламистов тексты к уникоду очень часто не имеют никакого отношения, а вот для сеошников некоторых любые из них важнее, чем немцы.
20 авг 17, 18:28    [20737146]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
Aleksandr Sharahov, ну так вы с самого начала могли решать эту задачу! В чем у вас тогда вопрос?
Если вы можете решить ее через Delphi::hashMap - то решайте.

Но как верно заметил MasterZiv - проверьте локаль для каждой страны. Чтоб при конверсиях
строк не потерять ни одного символа. Это важно.
20 авг 17, 18:30    [20737148]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Dima T
Member

Откуда:
Сообщений: 13545
Андрей Александрович.
Есть свободные 3 тб те куда делать временные таблицы есть

Маловато если исходных данных 2 Тб. Но если дублей много, то может и хватит.

ИМХО БД тут лишняя. Алгоритм примерно такой просится:
1-й проход набираем данных сколько в память влезет, сортируем, сохраняем в файл №1, следующая порция - файл №2 и т.д.
Затем слияние сортированных блоков попарно. В процессе слияния дубли выкидываем.
В итоге будет один файл с уникальными отсортированными записями, а дальше его можно в БД, а можно как есть использовать, если надо только читать.

Например при 8 Гб оперативки получим 256 файлов. По загрузке диска: 1+8 циклов чтение-расчет-запись на диск. Для 18 Тб на скорости 100 Мб/сек потребуется 50 часов дискового IO. Можно потоковое сжатие использовать, gzip/deflate, тогда в несколько раз быстрее работа с диском будет и места меньше потребуется.
Первый этап, т.е. первичная сортировка блоков, будет тормозной из-за проца, т.к. там больше проц будет загружен, поэтому его лучше распараллелить по количеству ядер.
20 авг 17, 18:32    [20737151]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
mayton,

я много задач могу решить, но это вовсе не значит, что я должен решать каждую :-)
20 авг 17, 18:33    [20737153]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
Aleksandr Sharahov
mayton,

я много задач могу решить, но это вовсе не значит, что я должен решать каждую :-)

Ну ОК. На самом деле в вашей задаче интересен только 150Гб файл. Все остальное решается
как угодно... sort, uniq, база. И у меня для вас минимум два алгоритма. Было. Сейчас я
думаю что вам с Delphi+MSSQL сам бох велел залить в табличку с опцией IGNORE_DUP_KEY.

Тут я думаю траблы будут другие.
20 авг 17, 18:44    [20737165]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mikron
Member

Откуда: Germany / Stuttgart
Сообщений: 764
Aleksandr Sharahov
mikron,

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

Мне кажется ваше допущение не коректно, что запись равна слову язука. Автор сказал что запись содержит слово языка но не значит что она / запись состоит только из слова.
В любом случае ваше допущение не обяснит как автор набрал 2 тб данных.
20 авг 17, 18:44    [20737166]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
mayton
Aleksandr Sharahov
mayton,

я много задач могу решить, но это вовсе не значит, что я должен решать каждую :-)

Ну ОК. На самом деле в вашей задаче интересен только 150Гб файл. Все остальное решается
как угодно... sort, uniq, база. И у меня для вас минимум два алгоритма. Было. Сейчас я
думаю что вам с Delphi+MSSQL сам бох велел залить в табличку с опцией IGNORE_DUP_KEY.

Тут я думаю траблы будут другие.

Сорян. Не туда запостил ну вобщем-то к автору.
20 авг 17, 18:46    [20737169]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
schi
Member

Откуда: Москва
Сообщений: 2601
Жаль, что не удалось услышать начальника транспортного цеха.

Автор так ничего и не сказал, как организованы его 180 петабайт данных, из фраз "проверить дубликаты и скомпоновать данные" "Файлы представляют собой хранилища слов всех языков мира" и "собираюсь писать на Delphi" никак непонятна организация слов в файлах и дубликаты чего ему, автору, надо проверять.
Мне кажется, автору надо установить сумму вознаграждения и написать в форум "Работа".
20 авг 17, 18:47    [20737170]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
mikron
Aleksandr Sharahov
mikron,

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

Мне кажется ваше допущение не коректно, что запись равна слову язука. Автор сказал что запись содержит слово языка но не значит что она / запись состоит только из слова.
В любом случае ваше допущение не обяснит как автор набрал 2 тб данных.


Даже если запись занимает 60 байт, то 60 мегабайт в памяти - не проблема.
Плюс таблица 16 мегабайт.

Загрузка данных хеш-таблицу пройдет практически со скоростью чтения данных с диска,
а дубликаты отсеются в процессе загрузки.
20 авг 17, 18:50    [20737174]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Dima T
Member

Откуда:
Сообщений: 13545
Aleksandr Sharahov
mikron
пропущено...

Мне кажется ваше допущение не коректно, что запись равна слову язука. Автор сказал что запись содержит слово языка но не значит что она / запись состоит только из слова.
В любом случае ваше допущение не обяснит как автор набрал 2 тб данных.


Даже если запись занимает 60 байт, то 60 мегабайт в памяти - не проблема.
Плюс таблица 16 мегабайт.

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

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

Тут автору топика вопрос: какой ожидается размер результата после выкидывания дублей?
20 авг 17, 19:06    [20737190]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
Dima T
Это при условии что хэш таблица с результатом будет умещаться в памяти.
Если не будет - результата думаю будет не дождаться из-за постоянного свопа на диск.

Тут автору топика вопрос: какой ожидается размер результата после выкидывания дублей?


Ну почему не будет-то?

10^6 слов * 60 байт + 10^6 слов * 2 коэф * (4+4) байт < 100 * 10^6
20 авг 17, 19:11    [20737193]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mikron
Member

Откуда: Germany / Stuttgart
Сообщений: 764
mayton
Откуда вообще 60 байт? Вроде автор вообще не говорил ничего подобного.
И при чем здесь сортировка?

Автор не говорил, но от чего то надо отталкиватся.
Интересно было бы услышать автора сколько у него записей.
Второй вопрос хорош. Как найти / удалить дупликаты без полной сортировки?
Первый уже упомянутый вариант - хеш. Но не будет хорошо работать на большом кол-ве уникальных данных. Есть другие методы, но умеют ли базы данных такое ? Я так думаю что не умеют. А значит только сортировка. Верно?
20 авг 17, 19:12    [20737194]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
mikron
mayton
Откуда вообще 60 байт? Вроде автор вообще не говорил ничего подобного.
И при чем здесь сортировка?

Автор не говорил, но от чего то надо отталкиватся.
Интересно было бы услышать автора сколько у него записей.
Второй вопрос хорош. Как найти / удалить дупликаты без полной сортировки?
Первый уже упомянутый вариант - хеш. Но не будет хорошо работать на большом кол-ве уникальных данных. Есть другие методы, но умеют ли базы данных такое ? Я так думаю что не умеют. А значит только сортировка. Верно?


Не верно, я тут уже ссылку давал в 20736814, почитай.
Хеш-таблица отсекает 10^6 дубликатов из 2*10^6 объектов за доли секунды.
20 авг 17, 19:17    [20737199]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mikron
Member

Откуда: Germany / Stuttgart
Сообщений: 764
Aleksandr Sharahov
Dima T
Это при условии что хэш таблица с результатом будет умещаться в памяти.
Если не будет - результата думаю будет не дождаться из-за постоянного свопа на диск.

Тут автору топика вопрос: какой ожидается размер результата после выкидывания дублей?


Ну почему не будет-то?

10^6 слов * 60 байт + 10^6 слов * 2 коэф * (4+4) байт < 100 * 10^6


По тому что 10^ 6 это не обоснованное допущение.
Запись может содержать слово языка плюс ещё что то, пусть его перевод на другой язык.
Например:
allow;ru;разрешать
allow;ru;позволять
allow;de;erlauben
20 авг 17, 19:24    [20737205]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mikron
Member

Откуда: Germany / Stuttgart
Сообщений: 764
Aleksandr Sharahov
mikron
пропущено...

Автор не говорил, но от чего то надо отталкиватся.
Интересно было бы услышать автора сколько у него записей.
Второй вопрос хорош. Как найти / удалить дупликаты без полной сортировки?
Первый уже упомянутый вариант - хеш. Но не будет хорошо работать на большом кол-ве уникальных данных. Есть другие методы, но умеют ли базы данных такое ? Я так думаю что не умеют. А значит только сортировка. Верно?


Не верно, я тут уже ссылку давал в 20736814, почитай.
Хеш-таблица отсекает 10^6 дубликатов из 2*10^6 объектов за доли секунды.

Что конкретно не верно?
20 авг 17, 19:26    [20737206]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Dima T
Member

Откуда:
Сообщений: 13545
Aleksandr Sharahov
Dima T
Это при условии что хэш таблица с результатом будет умещаться в памяти.
Если не будет - результата думаю будет не дождаться из-за постоянного свопа на диск.

Тут автору топика вопрос: какой ожидается размер результата после выкидывания дублей?


Ну почему не будет-то?

10^6 слов * 60 байт + 10^6 слов * 2 коэф * (4+4) байт < 100 * 10^6

Мне непонятно откуда цифра 10^6 ? При 10^10 как твоя хэш-таблица отработает? ТС этот момент не пояснил, я не просто так вопрос добавил.
20 авг 17, 19:32    [20737215]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
azsx
Member

Откуда:
Сообщений: 721
автор
Что конкретно не верно?

В базе пастухова 1 млрд кеев (строк со словами) -- это около 60 гб файл. А ТС оперирует 2 тб данных. То есть в 33 раза больше.
20 авг 17, 19:36    [20737219]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
mikron
Aleksandr Sharahov
пропущено...


Ну почему не будет-то?

10^6 слов * 60 байт + 10^6 слов * 2 коэф * (4+4) байт < 100 * 10^6


По тому что 10^ 6 это не обоснованное допущение.
Запись может содержать слово языка плюс ещё что то, пусть его перевод на другой язык.
Например:
allow;ru;разрешать
allow;ru;позволять
allow;de;erlauben



Да все нормально.
Пусть слов в языке 2*10^6 - точно достаточно для любого языка.
Пусть под слово (только слово и ничего кроме) 32 байта - точно достаточно.
Всю остальную хрень не читаем из файла, для отбора дубликатов она не требуется.
Прочитаем ее на этапе формирования выходного файла.


mikron
Что конкретно не верно?


Неверно то, что хеш таблица не справится и нужна сортировка.

Сортировка, может, и потребуется перед выдачей результата, но не для отсева дубликатов.
20 авг 17, 19:40    [20737223]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
ВМоисеев
Member

Откуда: Редкино
Сообщений: 1818
>schi, сегодня, 10:40 [20736710]
>...Если не удалось, то значит дубль, если удалось, то записывать слово ...
А если так (для русского словаря слов):
1. берём SQLite
2. создаём таблицы с именами а, б, в ... я и одним текстовым полем
3. читаем исходные файлы по строкам
4. выделяем слова и переводим в нижний регистр
5. наличие слов проверяем в соответствующей таблице (по первой букве слова), нет - дописываем
6. сортируем результат в таблицах
7. сливаем таблицы
насчёт индексов - проверить

Если есть память - вместо таблиц использовать списки
20 авг 17, 19:43    [20737230]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
azsx
В базе пастухова 1 млрд кеев (строк со словами) -- это около 60 гб файл. А ТС оперирует 2 тб данных. То есть в 33 раза больше.


Это на всех языках, включая числа и другие абракадабры?
Сколько слов на самом большом человеческом языке?
На гигабайты пофиг.
20 авг 17, 19:45    [20737233]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
mikron
Автор не говорил, но от чего то надо отталкиватся.
Интересно было бы услышать автора сколько у него записей.
Второй вопрос хорош. Как найти / удалить дупликаты без полной сортировки?
Первый уже упомянутый вариант - хеш. Но не будет хорошо работать на большом кол-ве уникальных данных. Есть другие методы, но умеют ли базы данных такое ? Я так думаю что не умеют. А значит только сортировка. Верно?

Как вы любите сортировать! Дайте волю - отсортируете всю вселенную а потом выберете unique?

Подумайте на следующей идеей. Вам дан текстовый файл. 150Gb. В формате csv.

У вас на борту - 8Gb оперативы. Операционка съедает порядка 2Гб и полезных
для ваших нужд остается порядка 6Гб. Это и есть эффективное пространство
для игр с хешами.

Экспериментально я устанавливаю (к примеру) что в Delphi hash табличка 4Гб ключей
съедают 6Гб кучи. Накладные расходы тык-скыть.

Далее я решаю порезать 150Gb на куски (примерно одинаковые). Будем называть их
chunks. По 4Гб ключей. Но не линейно сверху вниз по csv. А по хеш-функции (к примеру
md5). Не суть важно какая функция.

Считаем сколько будет чанков.

150 / 4 = 37,5.


Округляем в большую сторону. 38 чанков. И делаем функцию. Типа.

int hash38(string key){
   return mod(MD5(key),38); 
}


Я утверждаю что эта функция мапит key в свой чанк всегда. Тоесть одинаковые
ключи всегда будут в одном чанке.

Далее - дело техники. За 1 проход по 150 Гб файлу мы создаем 38 (попугаев)
дисковых чанков. Чтоб дисковая подсистема не сдохла - буферизируем по максимуму.

Потом все 38 файлов обрабатываем через Delphi::hashTable и сливаем уникальные
в result.csv.

Вы спросите вопрос. А не будет ли повторов ключей между чанками. Я отвечу.
Не будет. На основании свойств моей волшебной функции.

И никакой сортировки. Как вам?
20 авг 17, 19:54    [20737243]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
azsx
Member

Откуда:
Сообщений: 721
автор
Это на всех языках, включая числа и другие абракадабры?
Сколько слов на самом большом человеческом языке?

Это реальные строки, которые (в теории) могут искать в поисковых системах. Например:
установка окон в москве
скачать windows бесплатно
и так далее. Выборка, типа:
установк и москв
скач и windows исключить бесплатно
в grep на 60 гб делаются на hdd за 10 минут, на sed за 12. Такой файл логично делить по числу реальных винтов в системе.
---
Мне не понятно, как Вы пришли к выводу, что ТС на 2 тб хранит только уникальные слова всех стран мира.
20 авг 17, 19:56    [20737245]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
azsx
автор
Что конкретно не верно?

В базе пастухова 1 млрд кеев (строк со словами) -- это около 60 гб файл. А ТС оперирует 2 тб данных. То есть в 33 раза больше.

А что это за база "Пастухова"? Кто этот замечательный человек?
20 авг 17, 19:57    [20737246]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mikron
Member

Откуда: Germany / Stuttgart
Сообщений: 764
Aleksandr Sharahov
mikron


По тому что 10^ 6 это не обоснованное допущение.
Запись может содержать слово языка плюс ещё что то, пусть его перевод на другой язык.
Например:
allow;ru;разрешать
allow;ru;позволять
allow;de;erlauben


Всю остальную хрень не читаем из файла, для отбора дубликатов она не требуется.

Интересный поворот мысли. Другими словами в моём примере вы удалите все строчки за исключением первой как дубликаты?
Вас ничего не смущяет?
20 авг 17, 20:00    [20737251]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
azsx
Это реальные строки, которые (в теории) могут искать в поисковых системах. Например:
установка окон в москве
скачать windows бесплатно


Тогда это немного не то, что есть у автора в качестве исходных данных.

azsx
Мне не понятно, как Вы пришли к выводу, что ТС на 2 тб хранит только уникальные слова всех стран мира.


Напротив, из его слов можно предположить, что у него есть некие тексты на языках народов мира.
20 авг 17, 20:03    [20737257]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
azsx
Member

Откуда:
Сообщений: 721
автор
А что это за база "Пастухова"?

Оффлайн база кеев для сеошников. Полезна для некоторых тематик.
автор
Кто этот замечательный человек?

Программист. ИНН 920156526734, он ИП https://egrul.nalog.ru/
20 авг 17, 20:05    [20737259]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
azsx
Member

Откуда:
Сообщений: 721
автор
Напротив, из его слов можно предположить, что у него есть некие тексты на языках народов мира.

Тогда я сдаюсь. Чо то шибко много тб для всех слов в мире.
20 авг 17, 20:06    [20737263]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
mikron
Aleksandr Sharahov
пропущено...
Всю остальную хрень не читаем из файла, для отбора дубликатов она не требуется.

Интересный поворот мысли. Другими словами в моём примере вы удалите все строчки за исключением первой как дубликаты?
Вас ничего не смущяет?


Нет, не смущает. Была задача удалить дубликаты - я удаляю.
Будет задача объединить - объединю.
Что не так? :-)
20 авг 17, 20:07    [20737264]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mikron
Member

Откуда: Germany / Stuttgart
Сообщений: 764
mayton
И никакой сортировки. Как вам?

Зачтено.
Вопрос в том, умеют ли DBMS такие и подобные методы? Я думаю что нет, и это мой аргумент против DBMS для этой задачи.
20 авг 17, 20:10    [20737268]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Dima T
Member

Откуда:
Сообщений: 13545
mayton
И никакой сортировки. Как вам?

Может и заработает, только 38 неправильная цифра, больше надо, учитывай служебную инфу и размер страницы 4 кб, т.к. при нехватке памяти все что касается чанка должно постоянно быть памяти, т.е. не должно быть свопа пока в хэш-таблицу грузится один чанк.
20 авг 17, 20:13    [20737272]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mikron
Member

Откуда: Germany / Stuttgart
Сообщений: 764
Aleksandr Sharahov
Была задача удалить дубликаты - я удаляю.
Что не так? :-)

Вобще-то вопрос был риторический но если вам не непонятно: вы удалили оригинальные данные а не дубликаты


allow;ru;разрешать
и не одно и то же что
allow;ru;позволять
и уж совсем не дубликат
allow;de;erlauben
20 авг 17, 20:23    [20737278]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
mikron
Aleksandr Sharahov
Была задача удалить дубликаты - я удаляю.
Что не так? :-)

Вобще-то вопрос был риторический но если вам не непонятно: вы удалили оригинальные данные а не дубликаты


allow;ru;разрешать
и не одно и то же что
allow;ru;позволять
и уж совсем не дубликат
allow;de;erlauben


Вобще-то, и ответ был риторический, но если вам не непонятно,
то без четкого определения дубликата спорить абсолютно бессмысленно.
20 авг 17, 20:25    [20737282]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
mikron
mayton
И никакой сортировки. Как вам?

Зачтено.
Вопрос в том, умеют ли DBMS такие и подобные методы? Я думаю что нет, и это мой аргумент против DBMS для этой задачи.

DBMS умеет по другому. Он бъет сложным и универсальным ударом который
называется B+Tree. Это дерево. Но особое. Оптимизированное для дисковых
блочных операций. И разумеется оно нелетает без прослойки LRU-подобного
кеша блоков.

По сути табличка с индексом решает эту задачу универсально и квази-линейно
масштабируется до 150 Гиг и до петабайт. Зависит от нашей жадности.
20 авг 17, 20:43    [20737306]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mikron
Member

Откуда: Germany / Stuttgart
Сообщений: 764
Aleksandr Sharahov
mikron
пропущено...

Вобще-то вопрос был риторический но если вам не непонятно: вы удалили оригинальные данные а не дубликаты


allow;ru;разрешать
и не одно и то же что
allow;ru;позволять
и уж совсем не дубликат
allow;de;erlauben


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

Ну и чудесно, теперь надеюсь вам понятно, что ваше утверждение что хеш-таблица прекрасно справится беспочвенно.
Как некоторые уже писал, зависит от количества уникальных ключей.
20 авг 17, 20:45    [20737307]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
mikron
Aleksandr Sharahov
пропущено...
Вобще-то, и ответ был риторический, но если вам не непонятно,
то без четкого определения дубликата спорить абсолютно бессмысленно.

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


Я и не утверждал, что хеш-таблица справится со всеми задачами, которые вы придумаете.

Я лишь считаю, что с задачей автора, как я ее понимаю, хеш-таблица справится.
20 авг 17, 20:51    [20737309]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
Dima T
mayton
И никакой сортировки. Как вам?

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

Заработает! Не сомневайся! Ученье Маркса правильно, потому что оно - верно!

Принципиально-то алгоритм рабочий?

А по сабжу... то что ты говоришь - это тонкая настройка структур данных. Я там по тексту упомянул
что на 4Г ключей (по суммарной длине) я резервирую аж 2Г служебной инфы. По моему
это более чем достаточно для всех "гранулярных" структур данных.
20 авг 17, 20:54    [20737310]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Dima T
Member

Откуда:
Сообщений: 13545
mayton
4Г ключей (по суммарной длине)

Ну откуда вы эти предположения берете? ТС ничего не сказал по этому поводу. Исходи из худшего: все значения уникальны.
20 авг 17, 20:59    [20737314]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
ПЕНСИОНЕРКА
Member

Откуда: Владимирская обл
Сообщений: 4447
Андрей Александрович.,
в словарях практически нет повторений статей по слову(помогала как-то форматировать в ворде 2 словаря)
все строки разные(длина статьи доходила до 9кб, причем заносилось сие в одну ячейку)

привожу пример --это может быть в одной записи
case сущcase [keɪs] сущ
fact • matter • argument • reality • thing • affair • deedслучайм, делоср, примерм
instance • example • precedent • case in point(instance, affair, example)
event • occasion • occurrenceкорпусм, кожухм
box • housing • enclosure • body • cabinet • chassis • corps • pencil case(housing)
causeчехолм, футлярм, ящикм, чемоданм, коробкаж, кейсм, сумкаж, крышкаж
lawsuit • court case • legal case(cover, box, bag, briefcase)
обстоятельствоср, фактм
(circumstance, fact)
больной, пациентм
(patient)
историяж, история болезни
(history)
заболеваниеср
(disease)
регистрм
(register)
вариантм
(option)
шкафм
(cabinet)
прецедентм
(precedent)
витринаж
(window)
падежм
(mortality)
доводым
положениеср
(situation)
контейнерм
(container)
кассетаж
(magazine)

так что для начала надо видимо создать индексные файлы(150гб будет много меньше )
при этом получим статистику --а сколько слов в словаре, средняя длина стать
--имя словаря
--язык
--порядковый номер в справочнике
--ключевое слово статьи

ведь может потребоваться пересобирать источники в другом порядке, можно сначала собрать мелочь,
получив единый(ничего не удаляя),а только потом сливать с базовым
20 авг 17, 21:02    [20737318]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Dima T
Member

Откуда:
Сообщений: 13545
mayton
Принципиально-то алгоритм рабочий?

Рабочий. При большом количестве ключей надо будет допилить распределение по чанкам.
20 авг 17, 21:05    [20737326]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
ПЕНСИОНЕРКА
Member

Откуда: Владимирская обл
Сообщений: 4447
mayton
Вам дан текстовый файл. 150Gb. В формате csv.

их хотя и не без проблем можно разбить на 15 по 1 гб, хотя если статьи длинные --- частей может быть и меньше

150гб --это не показатель
сколько это записей
20 авг 17, 21:05    [20737327]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
Aleksandr Sharahov
mikron
пропущено...

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


Я и не утверждал, что хеш-таблица справится со всеми задачами, которые вы придумаете.

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

Нет сомнений что справится. Есть просто разные оценки времени. Алгоритм который
я предложил делает минимум 2 full scan по 150 Гб пространству ключей (построение
38 чанков и работа с каждым из них отдельно).

Сортировка о которой говорили выше в такой постановке не то чтобы не возможна.
Она возможна. Но вангую что под капотом у утилит sort, unique, e.t.c лежит
знаметитая "дисковая сортировка слиянием" (она -же ленточная, она-же merge)
которая перелопатит наши 150 Гиг не один и не два а логарифм ... хер там от какого
числа итераций, количество которых будет определяться эффетивностью первой
фазы.

Поэтому когда мне говорят о сортировке 150 Гиг - я улыбаюсь.

Попробуйте...
20 авг 17, 21:07    [20737332]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
Dima T
mayton
4Г ключей (по суммарной длине)

Ну откуда вы эти предположения берете? ТС ничего не сказал по этому поводу. Исходи из худшего: все значения уникальны.

Дима так все чики-пики. Я беру worst-scenario!
Я беспокоюсь о том чтобы вы не получили out of memory error.
Все 4 Гига уникальны? Отлично. Они все лягут нормик в хеш-табличку.
Будет 50% дублей? Отлично. Они свернуться на 2-й фазе когда мы отработаем
всех 38 попугаев.
20 авг 17, 21:10    [20737336]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
ПЕНСИОНЕРКА
mayton
Вам дан текстовый файл. 150Gb. В формате csv.

их хотя и не без проблем можно разбить на 15 по 1 гб, хотя если статьи длинные --- частей может быть и меньше

150гб --это не показатель
сколько это записей

+1

Ваш поинт про сколько записей очень верный! И я его коснусь в моем втором алгоритме.
Который я опишу чуть позже если топик еще будет актуален.

Выше вы пишете про 15 по 1Гб? Вы хотели сказать 15 по 10Гб?
20 авг 17, 21:13    [20737341]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mikron
Member

Откуда: Germany / Stuttgart
Сообщений: 764
mayton
mikron
пропущено...

Зачтено.
Вопрос в том, умеют ли DBMS такие и подобные методы? Я думаю что нет, и это мой аргумент против DBMS для этой задачи.

DBMS умеет по другому. Он бъет сложным и универсальным ударом который
называется B+Tree.

Это детали реализации но суть останется - сортировка всех данных. это точно не лучше того что вы предложили.
Интересно что могут предложить монстры оптимизации от DBMS.
20 авг 17, 21:18    [20737353]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Dima T
Member

Откуда:
Сообщений: 13545
mayton
Все 4 Гига уникальны? Отлично. Они все лягут нормик в хеш-табличку.
Будет 50% дублей? Отлично. Они свернуться на 2-й фазе когда мы отработаем
всех 38 попугаев.

Изначально озвучено 2 Тб, считай что они все уникальны, ну или упрости до 50%, т.е. 1 Тб уникальных. Какие 4 Гб?

хэш-таблица на 2 Тб имеет право на жизнь, только надо ОС оповестить чтобы она не убила прогу запросившую столько памяти и память с умом использовать, т.е. чтобы не постоянный своп, а нужное в большинстве случаев оказывалось уже отраженным в физическую память.
20 авг 17, 21:25    [20737363]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
mikron
mayton
пропущено...

DBMS умеет по другому. Он бъет сложным и универсальным ударом который
называется B+Tree.

Это детали реализации но суть останется - сортировка всех данных. это точно не лучше того что вы предложили.
Интересно что могут предложить монстры оптимизации от DBMS.

Они не сортируют. Они - строют дерево. Согласись - постановка
звучит как-то по другому.

А если ты сделаешь

SQL> SELECT dictinct word FROM fucken150GigTableDictionary

и при этом word будет не проиндексирован - то оптимизатор DBMS (Oracle - к примеру)
автоматически сольет всю выборку в табличное пространство TEMP. Потом отсортирует
теми-же алгоритмами что и мы обсуждали и потом выдаст курсор из этого TEMP
пространства временных упорядоченных данных.

Ничто не ново!

Поэтому безсмысленно спрашивать что дескыть DBMS-вендор предложит. Мы - разрабатываем
задачу. И мы отвечаем за эффективность ее решения.
20 авг 17, 21:28    [20737365]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
Dima T
mayton
Все 4 Гига уникальны? Отлично. Они все лягут нормик в хеш-табличку.
Будет 50% дублей? Отлично. Они свернуться на 2-й фазе когда мы отработаем
всех 38 попугаев.

Изначально озвучено 2 Тб, считай что они все уникальны, ну или упрости до 50%, т.е. 1 Тб уникальных. Какие 4 Гб?

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

Ну... здесь без автора трудно что-то спорить и доказывать. Но насколько я понял его первый пост.
2 Тб - это все справочники всех языков. А 150Гб - это просто один из самых толстых справочников.

Нужно-ли гарантировать кросс-уникальность между справочниками? Я не знаю. Скорее всего нет.
Это должно быть гарантировано кодовой страницей. Финские слова не пересекаются со шведскими.

Если я ошибаюсь - то пускай ТС - откомментарит.
20 авг 17, 21:31    [20737372]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
Автор говорил о "списках слов на разных языках" и все.
20 авг 17, 21:39    [20737386]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
Делим на чанки 2Терабайта...
20 авг 17, 21:40    [20737389]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
schi
Member

Откуда: Москва
Сообщений: 2601
mayton
DBMS умеет по другому. Он бъет сложным и универсальным ударом который
называется B+Tree. Это дерево. Но особое. Оптимизированное для дисковых
блочных операций. И разумеется оно нелетает без прослойки LRU-подобного
кеша блоков.


Первый раз такую трактовку слышу, про оптимизацию с дисками. Не поделитесь источником ?
20 авг 17, 21:41    [20737392]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
schi
mayton
DBMS умеет по другому. Он бъет сложным и универсальным ударом который
называется B+Tree. Это дерево. Но особое. Оптимизированное для дисковых
блочных операций. И разумеется оно нелетает без прослойки LRU-подобного
кеша блоков.


Первый раз такую трактовку слышу, про оптимизацию с дисками. Не поделитесь источником ?

1) Ваша постановка вопроса меня удивляет. Если вы из сегмента It - то вы должны были проходить
курс алгоритмы и структуры данных. Там - дают вводную по деревьям (красные-чорные, бинарные,
тернарные, АВЛ) и в том числе B+Tree, N-того порядка. Последние просто являются
частным случаем предыдущих деревьев при условии что группа узлов (Nodes)
объединяются в дисковый блок (2/4/8/16K) массив и все операции с узлами
делаются в рамках блока. Это дает оптимальное использование I/O.

Один из производителей DBMS их описывает так.
B-tree indexes are the standard index type. They are excellent for highly selective indexes (few rows correspond to each index entry) and primary key indexes. Used as concatenated indexes, a B-tree index can retrieve data sorted by the indexed columns.

Далее по ссылке отрисовывается вся внутренняя структура.

https://docs.oracle.com/database/122/CNCPT/indexes-and-index-organized-tables.htm#CNCPT88834

Детально об этом пишут разные писатели. Джонатан Льюис. Том Кайт.

Решение нашей задачи в рамках DBMS я вижу так:

create table FuckenWordsDictionary(word VARCHAR2(2000) primary key) organization index;


Далее - наполняем этот справочник insert-ами и игнорируем ошибку ORA-00001. Отбрасываем дубли.

Profit.

2) По кешам.

Механизм кеша - это я сказал ниочом и обо всем. Практически все современные
DBMS используют разные варианты кешей. IBM DB2, Postgres e.t.c. А кто не использует
тот дурак и у того нет перформанса.

Поэтому моя фраза о кешах - это попадание пальцем в небо. Так-же как и
"Волга Впадает в Каспийское море".
20 авг 17, 22:01    [20737423]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
schi
Member

Откуда: Москва
Сообщений: 2601
mayton

Первый раз такую трактовку слышу, про оптимизацию с дисками. Не поделитесь источником ?

1) Ваша постановка вопроса меня удивляет. Если вы из сегмента It - то вы должны были проходить
курс алгоритмы и структуры данных. Там - дают вводную по деревьям (красные-чорные, бинарные,
тернарные, АВЛ) и в том числе B+Tree, N-того порядка. Последние просто являются
частным случаем предыдущих деревьев при условии что группа узлов (Nodes)
объединяются в дисковый блок (2/4/8/16K) массив и все операции с узлами
делаются в рамках блока. Это дает оптимальное использование I/O.

Один из производителей DBMS их описывает так.
B-tree indexes are the standard index type. They are excellent for highly selective indexes (few rows correspond to each index entry) and primary key indexes. Used as concatenated indexes, a B-tree index can retrieve data sorted by the indexed columns.

Далее по ссылке отрисовывается вся внутренняя структура.

https://docs.oracle.com/database/122/CNCPT/indexes-and-index-organized-tables.htm#CNCPT88834

Детально об этом пишут разные писатели. Джонатан Льюис. Том Кайт.

[/quot]

Ничего не понял. Кайта и Льюиса читал, с деревьями знаком несколько раньше, чем вышли книги Кайта и Льюиса же, и ни разу не слышал про оптимизацию использования деревьев с точки зрения ввода-вывода, поэтому и заитересовался.
20 авг 17, 22:09    [20737449]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
schi
Ничего не понял. Кайта и Льюиса читал, с деревьями знаком несколько раньше, чем вышли книги Кайта и Льюиса же, и ни разу не слышал про оптимизацию использования деревьев с точки зрения ввода-вывода, поэтому и заитересовался.

Вся дисковая оптимизация для дисков старого поколения (магнитных) базируется
на уменьшении количества чтений и записей блоков (db_blocks). Сам по себе блок может
варьироваться от 512 байт до 64к. Это зависит от ОС и архитектуры. Поэтому
все структуры данных такие как таблицы и индексы бьются на блоки и читаются
и сериализуются кусками кратными блоку. Это считается ТруЪ для всех DBMS.
20 авг 17, 22:23    [20737485]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
schi
Member

Откуда: Москва
Сообщений: 2601
mayton
schi
Ничего не понял. Кайта и Льюиса читал, с деревьями знаком несколько раньше, чем вышли книги Кайта и Льюиса же, и ни разу не слышал про оптимизацию использования деревьев с точки зрения ввода-вывода, поэтому и заитересовался.

Вся дисковая оптимизация для дисков старого поколения (магнитных) базируется
на уменьшении количества чтений и записей блоков (db_blocks). Сам по себе блок может
варьироваться от 512 байт до 64к. Это зависит от ОС и архитектуры. Поэтому
все структуры данных такие как таблицы и индексы бьются на блоки и читаются
и сериализуются кусками кратными блоку. Это считается ТруЪ для всех DBMS.


Да, я знаю, что Волга впадает в Каспийское море, но причем тут B-деревья ? :)
На уменьшении количества операций ввода-вывода направлена любая оптимизация, пока диски не быстрее памяти, увы.

Ждем автора, от него должна информация поступать, а то, может, ему и оптимизация не нужна вовсе.
21 авг 17, 10:49    [20737990]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Bred eFeM
Member

Откуда:
Сообщений: 525
mayton
Как вы любите сортировать! ... табличка 4Гб ключей ...
это на 1*10^9 или на 4*10^9 ключей?

Считаем сколько будет чанков.
там слова? - а значит буквы - 32*2+1 будет достаточно.
Итого, максимум 1,5*10^9 слова из 20 разных первых символов длиной 5 (байт), которые на основании свойств моей волшебной функции сортируются с выбрасыванием копий не дольше 2х(чтение-запись) диска.

И никакой сортировки. Как вам?
И что с этим неупорядоченным 150G "как вам" делать дальше? Индексы строить, хеши считать...
21 авг 17, 11:50    [20738157]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
Я своё мнение кажется сказал в первом посте. Грузить в базу.

А все остальное в топика - это игры разума. И я поддерживаю их ради дискурса.
21 авг 17, 13:45    [20738617]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
В продолжение топика. Для 150Гб файла в качестве метрики эффективности
алгоритма КМК мы должны брать за основу т.н. Full-Table-Scan (это в терминологии БД).

Или грубо говоря 1 проход чтением по нашему файлу. Full-File-Scan (если мы работаем
со своими самописными алгоритмами). Для краткости - FFS.

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

Как я уже говорил - ленточная сортировка - это сразу более чем несколько FFS.
Ванговать не буду. Это количество зависит от оперативы у вас на борту.
26 авг 17, 12:09    [20750928]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
Можно предложить симбиоз оптимистичного и пессимистичного 20737243 алгоритма.

Сначала оптимистично грузим данные в хеш-таблицу пока не накопится некоторое предельное количество различных ключей, например, 2*10^6.

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

Если же различных ключей много, например, 128*10^6, то мы рано или поздно достигнем лимит. В этом случае выгружаем промежуточные результаты в 128 файлов, расслоив данные по хеш-коду. Затем очищаем таблицу, загружаем новую порцию, снова расслаиваем и дописываем в те же файлы. Продолжаем до исчерпания исходных данных. На второй фазе алгоритма поочередно грузим каждый из 128 промежуточных файлов в хеш-таблицу (с другой хеш-функцией) и дописываем из нее данные в результирующий файл.
26 авг 17, 12:52    [20750974]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
Aleksandr Sharahov, +1

Я тоже об этом думал. Но у меня была идея такая. Мы (к примеру) имеем не 1 а аж минимум 3 разных
алгоритма унификации большого толстого грёбаного файла (big-fat-ugly-file (BFUF)).

И во всех трех алгоритмах всегда присутствует первая фаза FFS. Что мы будем делать в эту фазу?
Сразу много всего.
- анализировать сведенья (число строк. средняя длина. количество уникальных на тек.момент,
гистограммы и прочие характеристики текста. Языки кодировки.)
- параллельно строить hash-table или другую структуру данных полезную для distinct of BFUF.
- если при параллельной постройке hash-table мы вышли за какие-то разумные границы
расходов памяти - то процесс анализа продолжаем до конца.
26 авг 17, 13:03    [20750983]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
Alibek B.
Member

Откуда:
Сообщений: 3014
Андрей Александрович.
Есть текстовые данные - порядка 2 тб в виде набора файлов ( файлы от 200 мб до 150 гб )
Задача проверить все файлы и удалить дубликаты ( а так же скомпоновать данные )

Что является записью (по которой выявляются дубликаты)?
Весь файл? Строка? Слово?
Если строка или слово, то необходимости использования БД я пока не вижу.
Нужно проиндексировать записи в имеющихся файлах, упорядочив их по языку и алфавиту.
При наличии индексов работать с этими файлами или выгрузить обработанные и отсортированные данные будет легче.
А удалять из середины 150ГБ файла несколько строк-дубликатов может быть накладно.
26 авг 17, 13:37    [20751007]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
Alibek B.
А удалять из середины 150ГБ файла несколько строк-дубликатов может быть накладно.
26 авг 17, 14:25    [20751050]     Ответить | Цитировать Сообщить модератору
 Re: Работа с большими данными  [new]
mayton
Member

Откуда: loopback
Сообщений: 39783
Всем заинтересованным.

Тема имеет логическое продолжение здесь Тяпничная унификация
9 сен 17, 17:27    [20783917]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2 3 4 5      [все]
Все форумы / Программирование Ответить