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

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

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

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

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

Откуда:
Сообщений: 13187
Андрей Александрович.
Есть свободные 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

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

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

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

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

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

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

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

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

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

Откуда: loopback
Сообщений: 38817
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

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

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

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


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

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

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

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


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

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

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

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

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

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


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

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

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

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

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

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


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

Откуда: Germany / Stuttgart
Сообщений: 760
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
Сообщений: 760
Aleksandr Sharahov
mikron
пропущено...

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


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

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

Откуда:
Сообщений: 13187
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

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

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

Откуда: Москва
Сообщений: 1707
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

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

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

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


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

Откуда: loopback
Сообщений: 38817
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

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

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

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

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

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

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


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


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

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

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


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

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


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