основной форум
Архив сообщений 2004-2006 года

Алгоритмы, методы, исходники


Алгоритмы >> Сортировка и поиск

Страницы: 1
ExtEEd
здесь был не раз


Рег.: 01/21/06
Сообщений: 28
Обработка большого массива
      #11874 - 08/20/06 07:28 AM

Имеется файл размерами примерно 16 гигабайт, содержащий числа. требуется выяснить, есть ли там одинаковые, и если есть, то надо найти хотя бы одно такое число. Подскажите пожалуфста метод обработки массива такого объёма.

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Studens
новичок


Рег.: 08/20/06
Сообщений: 5
Re: Обработка большого массива [Re: ExtEEd]
      #11876 - 08/20/06 11:43 PM

В ответ на:

Имеется файл размерами примерно 16 гигабайт, содержащий числа. требуется выяснить, есть ли там одинаковые, и если есть, то надо найти хотя бы одно такое число. Подскажите пожалуфста метод обработки массива такого объёма.



Сортировать быстрой сортировкой, затем найти повторы.


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
MBo
опытный
*****

Рег.: 08/25/04
Сообщений: 204
Из: Новосибирск
Re: Обработка большого массива [Re: ExtEEd]
      #11878 - 08/21/06 12:53 AM

Использовать один из методов внешней сортировки. Сортировка слиянием, например, легко модифицируется для такого случая.
А какого типа числа?


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Studens
новичок


Рег.: 08/20/06
Сообщений: 5
Re: Обработка большого массива [Re: ExtEEd]
      #11897 - 08/23/06 08:27 AM

Ура! Кажется, можно сделать всё за два прочтения файла! Правда, прога для частного случая: файл размером ровно 2^34 байт, содержащий ровно 2^32 dword'ов.
Code:

program bigfile;
var
buf:array[0..65535] of dword;
cnt:array[0..65535] of longint;
i,j:longint;
low_bytes:word;
f:file;
begin
assign(f,'bigfile');reset(f,65536);
for i:=0 to 65535 do
cnt[i]:=0;
for i:=0 to 65535 do begin
blockread(f,buf,1);
for j:=0 to 65535 do
inc(cnt[lo(buf[j])]);
end;
for i:=0 to 65535 do
if cnt[i]>65536 then begin
low_bytes:=i;
break;
end;
seek(f,0);
for i:=0 to 65535 do
cnt[i]:=0;
for i:=0 to 65535 do begin
blockread(f,buf,1);
for j:=0 to 65535 do
inc(cnt[hi(buf[j])]);
end;
close(f);
for i:=0 to 65535 do
if cnt[i]>1 then begin
writeln(dword(dword(i)*65536+dword(low_bytes)));
break;
end;
end.


Я не проверял её в действии, лень создавать такой гигантский файл.

Редактировал Studens (08/23/06 08:32 AM)


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
ExtEEd
здесь был не раз


Рег.: 01/21/06
Сообщений: 28
Re: Обработка большого массива [Re: MBo]
      #11898 - 08/23/06 08:35 AM

все числа 4х байтные

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
ExtEEd
здесь был не раз


Рег.: 01/21/06
Сообщений: 28
Re: Обработка большого массива [Re: Studens]
      #11899 - 08/23/06 08:38 AM

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

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
_МГ_
новичок
*****

Рег.: 08/14/06
Сообщений: 16
Из: Санкт-Петербург
Re: Обработка большого массива [Re: ExtEEd]
      #11901 - 08/23/06 12:36 PM

Ну и что?
4 байта это числа от 0 до 2^32. Просто заведём массив [0..2^32] и забьём его нулями. Проходим файл и смотрим: если в элементе массива с индексом текущего числа стоит 0 то такого еще не было, ставим туда 1. Если там один то значит такое было, о чём сообщаем и радуемся.
2^32 это 4 гига. Если это кажется много то можно банально написать битовое сжатие (запоминать не в байте а в бите было ли такое число), тогда памяти нужно будет 4гига/8 = 512метров. Столько то уж найтись должно...


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Studens
новичок


Рег.: 08/20/06
Сообщений: 5
Re: Обработка большого массива [Re: ExtEEd]
      #11904 - 08/23/06 07:08 PM

Извините, в моей программе я пропустил одну важную строчку:
Code:

program bigfile;
var
buf:array[0..65535] of dword;
cnt:array[0..65535] of longint;
i,j:longint;
low_bytes:word;
x:boolean;
f:file;
begin
assign(f,'bigfile');reset(f,65536);
for i:=0 to 65535 do
cnt[i]:=0;
for i:=0 to 65535 do begin
blockread(f,buf,1);
for j:=0 to 65535 do
inc(cnt[lo(buf[j])]);
end;
x:=false;
for i:=0 to 65535 do
if cnt[i]>65536 then begin
low_bytes:=i;
x:=true;
break;
end;
if not x then begin
close(f);
halt;
end;
seek(f,0);
for i:=0 to 65535 do
cnt[i]:=0;
for i:=0 to 65535 do begin
blockread(f,buf,1);
for j:=0 to 65535 do
if lo(buf[j])=low_bytes then {Пропустил эту строчку}
inc(cnt[hi(buf[j])]);
end;
close(f);
for i:=0 to 65535 do
if cnt[i]>1 then begin
writeln(dword(dword(i)*65536+dword(low_bytes)));
break;
end;
end.


Идея такая: если каждое число встречается только по одному разу, то каждая комбинация младших байтов должна встречаться ровно 65536 раз. Если это не так, то есть повторы.
Находим любую комбинацию младших байтов low_bytes, которая встречается чаще, чем 65536 раз. Среди чисел, которые встречаются более одного раза, обязательно будет число с равными low_bytes младшими байтами.
Второй проход: теперь перебираем числа с равными low_bytes младшими байтами и находим первое, которое встречается более одного раза.
Конечно, можно использовать битовый массив, но для этого частного случая можно обойтись и меньшим объёмом памяти.


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
kia
новичок
*****

Рег.: 06/12/06
Сообщений: 21
Re: Обработка большого массива [Re: Studens]
      #11906 - 08/23/06 08:48 PM

В ответ на:

Идея такая: если каждое число встречается только по одному разу, то каждая комбинация младших байтов должна встречаться ровно 65536 раз. Если это не так, то есть повторы.



Повторы могут быть даже если младшие 16 бит принимают все возможные значения по 65536 раз.
Например, представь себе файл, состоящий из чисел 0,1,2,...,65535, повторенных 65536 раз.


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Studens
новичок


Рег.: 08/20/06
Сообщений: 5
Re: Обработка большого массива [Re: kia]
      #11907 - 08/23/06 09:28 PM

В ответ на:

Например, представь себе файл, состоящий из чисел 0,1,2,...,65535, повторенных 65536 раз.



Действительно, программа не будет работать.
Интересно, верно ли такое утверждение: если в файле размером 16Гб, содержащем 32-х разрядные числа, имеются повторяющиеся числа, то после подсчёта частот младших и старших 16-битных слов по отдельности встретятся частоты, большие 65536?
Code:

program bigfile;
var
buf:array[0..65535] of dword;
cntl,cnth:array[0..65535] of longint;
i,j:longint;
f:file;
begin
assign(f,'bigfile');reset(f,65536);
for i:=0 to 65535 do begin
cntl[i]:=0;
cnth[i]:=0;
end;
for i:=0 to 65535 do begin
blockread(f,buf,1);
for j:=0 to 65535 do begin
inc(cntl[lo(buf[j])]);
inc(cnth[hi(buf[j])]);
end;
end;
for i:=0 to 65535 do
if (cntl[i]>65536)or(cnth[i]>65536) then begin
writeln('YES'); {В файле есть повторы!}
break;
end;
close(f);
end.


Если верно, то можно, всё-таки, обойтись без сортировки.


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
SergeyevАдминистратор
заслуженный
****

Рег.: 07/31/04
Сообщений: 1361
Из: Россия, Самара
Re: Обработка большого массива [Re: Studens]
      #11910 - 08/23/06 09:52 PM

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

Вот и придумайте проверку с помощью xor или еще какую-то хитрую.


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
ExtEEd
здесь был не раз


Рег.: 01/21/06
Сообщений: 28
Re: Обработка большого массива [Re: Sergeyev]
      #11916 - 08/24/06 01:21 AM

я согласен, что нечто подобное типа xor можно придумать. но этим можно установить лишь факт наличия совпадений. А надо ещё и найти эти совпадения...

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Makoed
здесь был не раз


Рег.: 01/31/06
Сообщений: 36
Из: IAI/Donetsk/Ukraine
Re: Обработка большого массива [Re: ExtEEd]
      #12040 - 09/06/06 01:52 AM

В ответ на:

Имеется файл размерами примерно 16 гигабайт, содержащий числа. требуется выяснить, есть ли там одинаковые, и если есть, то надо найти хотя бы одно такое число. Подскажите пожалуфста метод обработки массива такого объёма.



Как правильно подметили выше, каждое число надо кодировать битом. Получится 512Мбайт. Если внимательно прочитать условие, то достаточно найти единственное число. Алгоритм:
Выделяем 512МБ, забиваем нулями.
в цикле считываем все числа, при считывании числа проверяем бит[в нашей области памяти 512 МБ], равный порядковому номеру числа. Бит инвертируем. Если бит был установлен в 1, то мы нашли требуемое число, оно повторяется дважды.
Общее количество повторений легко найти тем же методом.
А вот поиск количества повторений для ВСЕХ чисел - задач стремная. Либо много памяти, либо много операций ввода-вывода...

--------------------
оптимизация... всего...


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Страницы: 1



Дополнительная информация
0 зарегистрированных и 335 анонимных пользователей просматривают этот форум.

Модератор:  Илья Кантор, PAV, Sergeyev 

Распечатать тему

Права
      Вы не можете создавать новые темы
      Вы не можете отвечать на сообщения
      HTML выключен
      UBBCode включен

Рейтинг:
Просмотры темы: 15494

Rate this topic

Переход в