Как исключить повторение записей в большом списке?

Question

[PO6OT]

Допустим есть такой код:

<?php
function getlist($string){
 if($string>0 && file_exists('./list.txt') && filesize('./list.txt')>=($string*2)){
  $list=fopen('./list.txt', 'a+');
  fseek($string*2-2);
  return fgets($list, 1);
 }
}

function putlist($data){
 if($data){
  $data=substr($data, 0, 1);
  file_put_contents('./list.txt', $data."\n", FILE_APPEND);
 }
}

Это упрощённый вариант, нет блокировок.
Тут вводимая строка сокращается до одного символа, но в реальности будет больше и строк будет много (list.txt больше 1 ТБ).

Как избежать повторения строк без потери производительности?

Можно попробовать так:

$data=$_GET['data']; //$data=='d';
for($i=1; $d=getdata($i), $d; $i++){
 if($d===$data){
  $cancel=true;
  break;
 }
}
if(!$cancel)
 putdata($data);

Но при больших объёмах данных такой способ не подходит.
Как, например, google убирает повторяющиеся ссылки из индексирования?

Answer 1

[Алексей Ostin]

Вам для разового применения (почистить базу) или для постоянного использования?

• Можно разбить весь объем на пачки и применить подход map-reduce (как раз как Google)
  
• Можно один раз пройтись по всем данным и построить индекс, чтобы использовать его в дальнейшем
  
• А можно просто положить все данные в какую-либо базу данных, поддерживающую этот функционал из коробки
  

Comments

[PO6OT]

по примеру решения разве не понятно, что надо на лету?

[Алексей Ostin]

Вадим Егоров: создавайте индекс. Если бы вы STDIN парсили - было бы понятно, что на лету. А так - просто файл какой-то

[PO6OT]

Алексей Ostin: а как индекс поможет находить строку с определённым содержанием?
я в технологиях БД не разбираюсь, объясните, что за индекс

[PO6OT]

Алексей Ostin: вы уверены, что MapReduce это то, что мне нужно?
По моему, он будет не быстрее моего способа.
А распараллеливания я там не заметил. Может я не на те статьи попал.

[Алексей Ostin]

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

Кстати говоря, возможно, вам моможет стандартная POSIX-утилита uniq.

[PO6OT]

Алексей Ostin: дело в том, что длинна строки меньше 32 байт

[PO6OT]

Алексей Ostin: uniq применима только после добавления в файл повторения, а мне надо проверить на уникальность строку до её добавления в список

[PO6OT]

Алексей Ostin: я думаю, может сделать посимвольное дерево?
типа есть такие строки:

asd
aft
bsd

создаётся дерево:

a[ s[ d ] f[ t ] ] b[ s[ d ] ]

нужно вставить строку ast (+ найдено, - не найдено):

+a[ +s[ -t ] ]

[Алексей Ostin]

А алфавит заранее известен? 32 байта - это 10^77 (2^(32*8)) уникальных бинарных значений - в память наверняка не влезет. md5, например - вдвое меньше

Более того, PHP-структура займет еще больше в памяти. Если есть уверенность, что список всех уникальных значений влезет в память - достаточно просто ключей (array('asd' => null)).

И еще раз про готовые утилиты:
sort -us -o uniq.txt list.txt

[Алексей Ostin]

Про uniq только сейчас прочитал. Если данные только планируются, почему не писать в базу? Шардинг + уникальный индекс. Про производительность вставки данных в уникальный индекс, например, mysql dba.stackexchange.com/questions/34837/unique-inser...

[PO6OT]

Алексей Ostin: я это хочу для хранения ссылок для индексации
там же террабайты одних только ссылок
уверены, что будет нормально работать?

[Алексей Ostin]

Будет у вас таблица с доменами (ну не думаю, что больше 30 млн насобираете) - это фигня. Нормально шардится по зоне. А таблица с путями отлично шардится по доменам.

Можно попробовать nosql какой-нибудь. Apache Lucene (Elasticsearch), например.

[Алексей Ostin]

расскажите, как терабайт насобираете :)