Сравнение стоимости одного списка внутри гигантского списка двух измерений в python, самый быстрый способ? - PullRequest
Новая
       6

Сравнение стоимости одного списка внутри гигантского списка двух измерений в python, самый быстрый способ?

1 голос
/ 01 декабря 2010

Я хочу сравнить, если значение одного списка существует в значении другого списка. Они огромны (50 тыс. + Элементов из базы данных).

EDIT:

Я также хочу отметить запись, которая дублируется, как duplicate = True и сохранить ее в таблице для последующего использования.

вот как списки: 

n_emails=[db_id,checksum for id,checksum in search_results]
#I want to compare checksum if exist inside same list or other list and retrieve id (db_id , if exist)
#example : n_emails= [[1,'CAFEBABE010'],[2,'bfeafe3df1ds],[3,'deadbeef101'],[5,'CAFEBABE010']] 
#in this case i want to retrive id 1 and 5 coz they are same checksum

for m in n_emails:
    dups=_getdups(n_emails,m[1],m[0])           
    n_dups=[casesdb.duplicates.insert( **dup ) for dup in dups]
    if n_dups:
        print "Dupe Found"
        casesdb(casesdb.email_data.id == m[0]).update(duplicated=True)

def _getdups(old_lst,em_md5,em_id):
    dups=[]
    for old in old_lst:
        if em_md5==old[0] and old[1]!=em_id:
            dups.append(dict(org_id=old[1],md5hash=old[0],dupID=em_id,))
    return dups

Но это кажется слишком длинным и в большом списке (50k против 50k записей +). Он работал более 5000 секунд и никогда не выполнялся, кажется, бесконечный цикл? Сервер, на котором я работаю, имеет 4 ГБ оперативной памяти и 4 ядра. Очевидно, я делаю что-то не так.

Пожалуйста, помогите .. большое спасибо!

РЕШИТЬ:

Dict Index Mapping намного быстрее! (Когда таблица mysql не проиндексирована, прошу заметить, что я не тестировал индексированную таблицу).

Его 20 секунд против 30 миллисекунд = 20 * 1000/30 = 666 раз! LOL

Ответы [ 4 ]

2 голосов
/ 01 декабря 2010

самый быстрый способ - использовать диктовку, подобную этой: 

n_emails= [[1,'CAFEBABE010'],[2,'bfeafe3df1ds'],[3,'deadbeef101'],[5,'CAFEBABE010']]

d = {}
for id, hash in n_emails:
    if hash not in d:
        d[hash] = [id]
    else:
        d[hash].append(id)

for hash, ids in d:
    if len(ids) > 1:
       print hash, ids

это почти алгоритм для хеш-соединения 

for hash, count in select hash, count(id) as num from emails group by num having num > 1:
    first = None
    for index, id in enumerate(select id from emails where hash=hash sort by desc id):
        if index == 0:
            first = id
            continue
        update emails set duplicate=first where id=id

будет решением sql / python в этом, я беру дубликат столбца и использую его для хранения того сообщения, которое считается дубликатом

таблица адресов электронной почты будет по крайней мере: 

create table emails (id, hash, duplicate default null)
2 голосов
/ 01 декабря 2010

Что вы делаете неправильно:

  • Вероятно, вы можете получить результат непосредственно из базы данных. Это намного быстрее, чем Python.
  • Вы выполняете линейный поиск контрольных сумм, что означает, что каждая из 50k записей сравнивается с каждой других 50k записей ... это огромное количество сравнений.

Что вам нужно сделать, это построить индекс по контрольным суммам. Сделайте дикт, который отображает checksum -> entry. Когда вы вставляете записи, проверьте, существует ли контрольная сумма, если это так, то запись является дубликатом.

Или вы просто используете свою базу данных, они любят индексирование.

2 голосов
/ 01 декабря 2010

Вам лучше искать дубликаты с SQL. Например, см. на этой странице, где описано, как найти дубликаты .

Перенос всех этих результатов в Python и их обработка никогда не будут очень быстрыми, но если вам необходимо, лучше всего иметь словарь контрольных сумм для идентификаторов: 

got_checksums = {}
for id, checksum in emails:
    if checksum in got_checksums:
        print id, got_checksums[checksum]
    else:
        got_checksums[checksum] = id
1 голос
/ 02 декабря 2010

Наконец-то, благодаря всем ответам, я обнаружил, что отображение dict безумно быстро!Гораздо быстрее, чем запросы SQL.

Вот мой тест SQL-запросов (он будет казаться неудобным, но это синтаксис запросов Web2pyDAL).

Я тестировал и 3500 записей, и только dictсопоставление более 250000 записей.

print "de_duping started at %s" % str( datetime.datetime.now() )

dupe_n = 0
l_dupe_n = 0
for em_hash in n_emails:
    dup_ids=casesdb(casesdb.email_data.MD5Hash==em_hash[1]).select(casesdb.email_data.id)
    if dup_ids>1:
        dupe_n+=1

print "Email Dupes %s" % (dupe_n)
print "Local de_duping ended at %s" % str( datetime.datetime.now() )

Результат в: 

de_duping started at 2010-12-02 03:39:24.610888
Email Dupes 3067
Local de_duping ended at 2010-12-02 03:39:52.669849

около 28 секунд. Вот карта индексации на основе диктов, основанная на Дане Д 

    print "de_duping started at %s" % str( datetime.datetime.now() )
    for id, hash in em_hash:

            if hash not in dedupe_emails:

                dedupe_emails[hash] = [id]
            else:

                dedupe_emails[hash].append( id )
                dupe_n += 1
                casesdb( casesdb.email_data.id == id ).update( duplicated = True )

    print "Email Dupes %s" % (dupe_n)
    print "Local de_duping ended at %s" % str( datetime.datetime.now() )

, в результате: 

de_duping started at 2010-12-02 03:41:21.505235
Email Dupes 2591 # this is accurate as selecting from database regards first match as duplicate too
Local de_duping ended at 2010-12-02 03:41:21.531899

только что?30 мс!

и давайте посмотрим, что было сделано против дедупликации 250 тыс. Записей! 

de_duping at 2010-12-02 03:44:20.120880
Email Dupes 93567 
Local de_duping ended at 2010-12-02 03:45:12.612449

Менее, чем за минуту !!

Спасибо за все ответы, я быЯ бы хотел выбрать всех, кто указал мне правильный путь, но Дэн Д. дал мне самый подробный ответ!Спасибо Дэн!

...