Быстрое индексирование 140 млн. текстовых ключей

Библиотека - MPI. Если есть под рукой кластер (-:

Непременно проиндексировать, или только удалить дубликаты? Эсли последнее, то Цэ (можно ++) в зубы, Кнута туда же -- и реализуй кую-нить внешнюю сортировку...

Гарантий и тут никаких, но, похоже, удинственная надежда...

С уважением -- Смоляное Чучелко

www.risearch.org, только ничего ты сделать не сможешь с этой базой...

А если разбить сперва на n содержащих 140000000/n записей, потом в каждой провести сортировку .. а дальше плясать от результата сортрировки ?/может оказаться что уникальых записей ~100000000, к примеру ?/
$echo.
P.s. Кажется на ЛОРе новость пробегала о Мускуле /или другой какой-то БД для кластеров.../
$echo.

140e6/(5*3600)=7777 операций с ключами в секунду. При размере ключа 32 символа - это порядка 250000 операций с символами. Могу спорить, что 1e9герцовый процессор сделает это с легкостью - аж 4 тысячи тактов на символ. Вот только памяти/адресного пространства нужно немало. Есть у тебя машинка с 64битным камнем и несколькими гигами памяти - получится.

Но я бы пользовал не хеш. Скорее trie какой-нибудь.

Что пришло на ум во время пития кофе:

-------------------------------------------------- delay1.py
def flush(filo, dict):
k = dict.keys()
k.sort()
f = file('part%04d.txt' % (filo), 'w')
for i in k:
print >> f, i
f.close()
print fileno

f = file('raw.txt')
i=0
fileno = 0
dict = {}
for line in f:
dict[line[:-1]] = 1
i = i + 1
if i==1000*1000:
flush(fileno, dict)
dict = {}
fileno = fileno + 1
i = 0
f.close()

-------------------------------------------------- delay2.py
fs = [file('part%04d.txt'%i) for i in range(140)]

dict = {}
for f in fs:
l = f.readline()[:-1]
while l in dict.keys():
l = f.readline()[:-1]
dict[l] = f

while len(dict)>0:
m = min(dict)
f = dict[m]
del dict[m]
l = f.readline()[:-1]
while l in dict.keys():
l = f.readline()[:-1]
dict[l]=f
print m

я не знаю как тут формат сохранить... если надо то повторю...

Короче делай раз около 20 минут.

Делай два примерно 100 мегабайт за 3 минуты или 2 часа на 4 гига.

Все решается простым питоном на раз безо всякой клястерной хренотени.

PS: однажды приходилось решать что то типа этого. Питон+кофе/перекур (сочитая по вкусу) все решает. Удачи.

Можно попробовать сбалансированные деревья, если конечно тебе потом в них что-либо искать нужно, сложность О(log_2(N)) для добавления, и столько же для поиска. Только что-то объем несколько пугающий (>4Gb) можно пробовать делить на куски, параллелится в легкую...