Контрольная сумма для списка номеров

У меня есть большое количество списков целых чисел. Я хочу проверить, дублирует ли какой-либо из списков. Я думал, что хорошим способом сделать это было бы вычисление базовой контрольной суммы, а затем только проверка элемента по элементу, если контрольные суммы совпадают. Но я не могу найти алгоритм контрольной суммы с хорошими свойствами, а именно:Контрольная сумма для списка номеров

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

Например, функция check_sum, которая возвращала разные номера в диапазоне [0,65536] для следующих 5 вызовов, была бы идеальной.

check_sum([1,2,3,4,5]) 
check_sum([1,2,3,5,4]) 
check_sum([5,4,3,2,1]) 
check_sum([1,2,3,4,4])

Я посмотрел на алгоритм контрольной суммы заголовка IPv4, который возвращает результат нужного размера, но не проверяет порядок так не то, что я ищу.

Я собираюсь реализовать его в python, но любой формат будет использоваться для алгоритма или указателя в хорошем справочном материале.

источник

2016-09-19 felih

Является ли хэш (кортеж ([1,2,3,4,5])) 'Недостаточно? – Tempux

Сколько списков и насколько они велики? –

Списки являются результатом алгоритма поиска, поэтому я стараюсь растянуть число списков, насколько я могу, возможно, 100k. Они будут до 100 долгих, в среднем 50. – felih

Вычислить контрольную сумму с hash():

checksums = \ 
    list(
     map(
      lambda l: 
       hash(tuple(l)), 
      list_of_lists 
     ) 
    )

Чтобы узнать, сколько дубликатов у вас есть:

from collections import Counter 

counts = Counter(checksums)

Чтобы составить уникальный список:

unique_list = list(dict(zip(checksums, list_of_lists)).values())

источник

2016-09-19 22:44:22 deeenes

Зачем вам писать этот многострочный 'list (map (lambda ...))' вместо понимания списка? –

@Stefan вы правы, но для меня это выглядит очень ясно, я сразу вижу ядро и выражение, и нам не нужно экономить на линиях :) – deeenes

Если вы хотите что-то домотканые , возможна версия контрольной суммы Флетчера.

def check_sum(l): 
    sum1 = sum2 = 0 
    for v in l: 
     sum1 = (sum1 + v) % 255 
     sum2 = (sum2 + sum1) % 255 
    return sum1*256 + sum2 

print(
    check_sum([1,2,3,4,5]), 
    check_sum([1,2,3,5,4]), 
    check_sum([5,4,3,2,1]), 
    check_sum([1,2,3,4,4]) 
)

источник

2016-09-20 16:32:44

Контрольная сумма для списка номеров

ответ

Смежные вопросы