Проблема нехватки памяти

← →
Павиа (2012-08-31 15:22) [40]

Хе-ХЕ. Задача на сортировку 22 файлов с 50 миллионов слов с индексами и их слияния и последующее удаление дублей.

На линуксе можно очень быстро сделать за час. Или на почти любой БД.

← →
Sha © (2012-08-31 15:33) [41]

как только люди жили без БД

← →
Дмитрий С © (2012-08-31 15:47) [42]

> На линуксе можно очень быстро сделать за час. Или на почти
> любой БД.
>

Да это задача из разряда не "Как сделать", а "Просто надо взять и сделать". Тут даже обсуждать то нечего.

← →
sniknik © (2012-08-31 16:01) [43]

> и последующее удаление дублей.
> На линуксе можно очень быстро сделать за час. Или на почти любой БД.
как однако линукс влияет на сознание... трудолюбие воспитывает.
у меня так даже мысли не возникло о "последующем" удалении, думал сразу, в одно действие, при добавлении "отсекать". способов хватает.

← →
Павиа (2012-08-31 18:14) [44]

Это не линукс. Это я просто на много проходную обработку подсел. Так алгоритм нагляднее получается чем потоковая обработка. Хотя иногда наоборот создает трудности.

← →
Студент (2012-08-31 18:19) [45]

Sha © (31.08.12 15:33) [41]

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

← →
Разведка (2012-08-31 18:31) [46]

Ответ для всех.
Да что бы я так жил как вы все говорите.
1. Не сама задачка сложна, а ее реализация. Я всех тонкостей не знаю, что работает быстрее, а что не быстрее, например незнал, что TADOTable - тормоз.
2. что плохого загрузить весь файл в память, есть память ее нужно использовать всю, при построчном чтении вот точно тормоза будут, диск как минимум читает блоками, а не байтами, а при чтении по одной строке в несколько байт это не рационально. для примера скопируй из файла "А" 50мб. в файл "Б" все по 1 байту и увидите сколько он будет копироваться по сравнению когда будете копировать большими блоками.

> Inovet © (31.08.12 10:19) [33]
> Вот поэтому 57 (или сколь там) суток считает.SELECT * FROM
> wordstabl WHERE words = :SFindДубли надо в запросе убирать,
> а не запрос на каждое слово.

Это как? Я не понимаю. Я так сделал по то, что Ассess слова в базе не учитывают регистр там слово Арбуз = арбуз = арбуЗ - это дубликаты, а для меня это разные слова и должны присутствовать в базе.

← →
Кукарямба (2012-08-31 18:35) [47]

> Нужно убить дубликаты сразу во всех словарях, а маленькие
> те что останутся объединить в большие словари.

Дональд Эрвин Кнут, Искусство программирования, том 3. Сортировка и поиск.

> не вмещается 350 миллионов строк

...

> и в них слова дублируются.

Это в каком это языке 350 миллионов слов? Пусть даже с дубликатами. Или там дубликатов дофига?

← →
Разведка (2012-08-31 18:40) [48]

> Кукарямба (31.08.12 18:35) [47]

Да! Есть! Слушаюсь! Капитан очевидность!

А еще нужно убить дубликаты не только внутри словарей, а и между словарями.

← →
Sha © (2012-08-31 18:40) [49]

> Разведка

на [39] ответь

← →
Разведка (2012-08-31 18:46) [50]

Каждое слово нужно считать уникальным если оно отличается хотя бы регистром, например,
1. Арбуз - уникальное
2. арбуз - тоже уникальное
3. аРбуз - тоже уникальное

И они не должны считаться дубликатами

> Поместятся ли эти уникальные значения в ОП?Зачем надо куда-
> то грузить?

- про это я не понял о чем речь

← →
Разведка (2012-08-31 18:51) [51]

> Разведка (31.08.12 18:46) [50]
> > Поместятся ли эти уникальные значения в ОП?

Если ОП имелось ввиду оперативная память, то от чего бы им туда не поместиться, сколько нужно столько ее и будет в данном случае у меня 4гб и еще 8гб могу добавить.

← →
Sha © (2012-08-31 18:57) [52]

1. Сколько уникальных значений должно остаться в конце концов?
10? 100? 100000?

2. Поместятся ли эти уникальные значения в ОП?
Или среднюю/максимальную длину слова приведи.

3. Зачем надо куда-то грузить?
Почему нельзя формировать результат в процессе чтения всех этих txt-файлов?

← →
DVM © (2012-08-31 19:13) [53]

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

← →
Разведка (2012-08-31 19:33) [54]

> Sha © (31.08.12 18:57) [52]
> 1. Сколько уникальных значений должно остаться в конце концов?
> 10? 100? 100000?2. Поместятся ли эти уникальные значения
> в ОП?Или среднюю/максимальную длину слова приведи.3. Зачем
> надо куда-то грузить?Почему нельзя формировать результат
> в процессе чтения всех этих txt-файлов?

Все просто.
1. неограничено
2. размер занимаемой памяти = сумме всех словарей - это теоретически 350 = 400 мб. в БД под строку выделено 32 байта + Ключ(счетчик).
3. Словари эти не просто слова, а база паролей поэтому они уникальны в базе уже писал >> Разведка (31.08.12 18:46) [50]

← →
картман © (2012-08-31 19:41) [55]

> 2. размер занимаемой памяти = сумме всех словарей - это
> теоретически 350 = 400 мб.

пароли по 1-2 однобайтовых символа? Или не 350 млн строк? 350 млн пользователей?

← →
Разведка (2012-08-31 19:42) [56]

> Inovet © (31.08.12 10:05) [31]
> TADOTable, всем пофиг. И методы соответсвующие. Про SQL
> не слышал никогда?

Заменил TADOTable на ADOQuery

Par := Query.Parameters.AddParameter; par.Name := "StrValue"; Par.DataType := ftString; par.Direction := pdInputOutput; Query.Parameters.ParamByName("StrValue").Value := st.Strings[j]; Query.SQL.Text := "INSERT INTO wordstabl (words) VALUES (:StrValue)"; Query.ExecSQL;

Скорость та же ничего не изменилось, и постепенно идет к уменьшению

← →
Sha © (2012-08-31 19:42) [57]

> Разведка

Ты противоречишь сам себе:

350 миллионов строк * 32 байта > приблизительно 350 мб

← →
Разведка (2012-08-31 19:49) [58]

> картман © (31.08.12 19:41) [55]
> > 2. размер занимаемой памяти = сумме всех словарей - это
> > теоретически 350 = 400 мб.пароли по 1-2 однобайтовых символа?
> Или не 350 млн строк? 350 млн пользователей?

сам то посчитай
пароли длиной 2-3 символа при алфавите a-z = 3^26; a-z + A-Z = 3^42 ну и т.д. там разной длины слова

← →
Inovet © (2012-08-31 19:55) [59]

> [57] Sha © (31.08.12 19:42)
> Ты противоречишь сам себе:

Да в самом начале про это говорили, похоже не понял автор.

← →
Разведка (2012-08-31 19:55) [60]

> > Разведка Ты противоречишь сам себе:350 миллионов строк
> * 32 байта > приблизительно 350 мб

Не противоречу
350 миллионов строк в файлах слловарей приблизительно каждый из них около 50 мгб их размер разный так как и слова разной длины, а вот в базе длина поля фиксирована по 32 байта. Выполняется такая операция из файлов .txt слова переносятся в БД при этом нужно убить дубликаты, так как во многих словарях повторы.

← →
картман © (2012-08-31 20:02) [61]

1 мегабайт = 1024 * 1024 байт
1 миллион = 1000 * 1000
*SCRATHC*
1 миллион строк = 1000 * 1000 строк

← →
Разведка (2012-08-31 20:07) [62]

> Разведка (31.08.12 19:55) [60]

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

← →
Sha © (2012-08-31 20:12) [63]

> Разведка

Тогда в чем проблема-то, 350мб свободно в ОП влезут.
Время обработки словарей = времени их чтения в ОП.

← →
картман © (2012-08-31 20:19) [64]

> Время обработки словарей = времени их чтения в ОП.

научи

← →
Sha © (2012-08-31 20:25) [65]

> картман

в процессе чтения помещаем данные в хеш-таблицу

← →
Разведка (2012-08-31 20:49) [66]

> Sha © (31.08.12 20:12) [63]
> > РазведкаТогда в чем проблема-то, 350мб свободно в ОП влезут.
> Время обработки словарей = времени их чтения в ОП.

А вот чего то не влазят, ексепшион вываливает. после загрузки 7-го словаря в память.

Общее количество словарей 25 по 50 млн. строк каждый приблизительно 45-55 мб. в сумме 1.2 гб. Значит я их пытался загрузить в TStringList, что бы объединить в один словарь и начать проверять на дубликаты другие дополнительные словари с этим гигантским, но после добавления в TStringList на 7 словаре происходит ошибка скажем, что нехватка памяти, хотя по всем видимым признакам памяти должно хватать с избытком ОП 3 Гб. на компьютере. Вот из-за этого и возникла эта ветка.

← →
Разведка (2012-08-31 20:53) [67]

> Разведка (31.08.12 20:49) [66]

А ~350 мб. это просто тот предел на котором возникает ошибка поэтому здесь и зациклились на этой цифре.

← →
Sha © (2012-08-31 20:54) [68]

> вот чего то не влазят

не так делаешь

если не устраивает [65], то с минимальными исправлениями своего алгоритма
можешь подгружать по одному словарю, удалять дубликаты, снова подгружать и т.д.

← →
Разведка (2012-08-31 21:22) [70]

> Sha © (31.08.12 21:02) [69]
> своего алгоритмаможешь подгружать по одному словарю, удалять
> дубликаты, снова подгружать и т.д.

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

> именно так и сделал как ты предлагаешь ,
> но задача теперь уперается в низкую скорость

не верю, код покажи

← →
Плохош (2012-08-31 21:38) [72]

> код покажи

испугаться хочешь?

← →
Разведка (2012-08-31 21:51) [73]

> Sha © (31.08.12 21:35) [71]
> > именно так и сделал как ты предлагаешь , > но задача теперь
> уперается в низкую скоростьне верю, код покажи

Может быть уже и не совсем так ведь каждый имеет свое на уме. Код я переделал кардинально и пошел путем который посоветовали эти участники

> DVM © (29.08.12 22:51) [9] и Inovet ©

Но впрочем, еще что то осталось. Не помню какой вариант окончательный или промежуточный. Я пытался один добавляемый словарь проверить с 25 другими словарями (т.е. они были базовыми) по очереди в цикле.
Здесь самая примитивщина никаких крутых алгоритмов оптимизации и хэшей т.д.
unit DicThreade; interface uses SysUtils, Windows, Classes, MsgLog; Type TThrStat = (TS_STARTED,TS_END); Type TTstatInfo = Record BaseDic : String; AddDic : String; DublCount : Integer; NewWords : Integer; CurCount : Integer; End; type TDicProc = class(TThread) Status : TThrStat; CurCount : Integer; BaseDic : String; AddDic : String; DublCount: Integer; AddCount : Integer; private FMsg : Cardinal; FWnd : THandle; FAList : TStrings; FBList : TStrings; protected procedure Execute; override; public Constructor Create(AList, BList: TStrings; Wnd:THandle; Msg: Cardinal); Constructor Destroy; end; implementation Uses Unit1; constructor TDicProc.Create(AList, BList: TStrings; Wnd: THandle; Msg: Cardinal); begin inherited Create(false); FWnd := Wnd; FMsg := Msg; FAList := TStringList.Create; FBList := TStringList.Create; FAList.Text := AList.Text; FBList.Text := BList.Text; end; constructor TDicProc.Destroy; begin inherited Destroy; FAList.Free; FBList.Free; end; procedure TDicProc.Execute; var Asl,Bsl,Nsl: TStrings; i,ACnt,BCnt,DublCnt,Cnt: Integer; s: string; begin { if FAList.Count = 0 then begin SendDebugMsgLastError("NewThread.Execute error:",GetLastError,0); Exit; end; } Status := TS_STARTED; try Asl := TStringList.Create; //Asl - Add String list Bsl := TStringList.Create; //Bsl - Base String lisl Nsl := TStringList.Create; //Tsl - Temp String List ACnt := 0; while Acnt <> FAList.Count do begin //SendDebugMsg("FAList = "+FAList.Strings[Acnt]); Asl.Clear; Asl.LoadFromFile(FAList.Strings[Acnt]); AddDic := FAList.Strings[Acnt]; Bcnt := 0; while Bcnt <> FBList.Count do begin //SendDebugMsg("FBList = "+FBList.Strings[BCnt]); BaseDic := FBList.Strings[BCnt]; Bsl.Clear; Bsl.LoadFromFile(FBList.Strings[BCnt]); Cnt := 0; While Cnt <> Asl.Count do begin CurCount := Cnt; if Bsl.IndexOf(Asl.Strings[Cnt]) = -1 then begin Nsl.Add(Asl.Strings[Cnt]); AddCount := Nsl.Count; Inc(Cnt); continue; end; Inc(DublCount); Inc(Cnt); end; Inc(BCnt); end; //Save Asl Result; inc(ACnt); end; finally Asl.Free; Bsl.Free; Nsl.Free; end; end; end.

> испугаться хочешь?

ага, фильмы пересмотрел все, что были )

← →
Разведка (2012-08-31 22:01) [75]

> Разведка (31.08.12 21:51) [73]

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

Сливаешь не так. Попробуй сортировку, а не IndexOf.

> Sha © (31.08.12 20:25) [65]
>
> > картман
>
> в процессе чтения помещаем данные в хеш-таблицу

не получится так же быстро

> Разведка (31.08.12 21:51) [73]

шикарно))
надеюсь, в FBList & FAList полные списки передаешь?

> картман © (31.08.12 22:06) [77]
> не получится так же быстро

Точно.
Процессор обрабатывает данные быстрее, чем происходит их чтение с жесткого диска )

> Процессор обрабатывает данные быстрее, чем происходит их
> чтение с жесткого диска )

да ну?

← →
Разведка (2012-08-31 22:19) [80]

> Sha © (31.08.12 22:01) [76]
> Сливаешь не так. Попробуй сортировку, а не IndexOf.

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

> картман © (31.08.12 22:06) [77]
> надеюсь, в FBList & FAList полные списки передаешь?

Туда только имена файлов словарей передавались. Добавляемые словари и базовые словари.

Проблема нехватки памяти Найти похожие ветки