Учитывая файл, содержащий 4,30 миллиарда 32-разрядных целых чисел, как мы можем найти число, которое появилось как минимум дважды?

Question

Я придумал алгоритм "разделяй и властвуй" для этого. Просто хотел узнать, сработает ли это или нет?

Первая середина вычисляется из целочисленного диапазона, т.е. (0+(1<<32-1))>>1, а затем применяется эта идея: диапазон чисел от начала до середины или от середины до конца всегда будет меньше чисел мы рассмотрим, как мы рассматриваем миллиардные числа, и определенно найдутся некоторые числа, которые будут повторяться, так как диапазон 32-битного целого числа намного меньше по сравнению с миллиардным числом.

def get_duplicate(input, start, end):  
  while True:
    mid = (start >> 1) + end - (end >> 1)
    less_to_mid = 0
    more_to_mid = 0
    equal_to_mid = 0
    for data in input:
        data = int(data, 16)
        if data < mid:
            less_to_mid += 1
        elif data == mid:
            equal_to_mid += 1
        else:
            more_to_mid += 1
    if equal_to_mid > 1:
        return mid
    elif mid-start < less_to_mid:
        end = mid-1
    elif end-mid < more_to_mid:
        start = mid+1

with open("codes\output.txt", 'r+') as f:
  content = f.read().split()
  print(get_duplicate(content, 0, 1<<32-1))

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

Answer 1

Ваш метод в порядке. Но вам, вероятно, нужно будет прочитать ввод много раз, чтобы найти ответ.

Вот вариант, который позволяет вам найти дубликат с небольшим объемом памяти, но вам нужно только прочитать вход дважды.

1. Инициализировать массив A[65536] целых чисел в ноль.
2. Читайте цифры по одному. Каждый раз, когда число x читать, добавить 1 в A[x mod 65536],
3. Когда чтение закончится, появится хотя бы один i такой, что A[i] строго больше, чем 65536, Это потому что 65536 * 63356 < 4.3 billion, Скажем A[i0] больше чем 65536,
4. Очистить массив A в ноль.
5. Прочитайте цифры еще раз, но на этот раз, только посмотрите на эти цифры x такой, что x mod 65536 = i0, За каждый такой x, добавлять 1 в A[x / 65536],
6. Когда чтение закончится, появится хотя бы один j такой, что A[j] строго больше, чем 1, Тогда число 65536 * j + i0 это окончательный ответ.

Answer 2

Память размером 2^32 бита не является чем-то особенным для современных систем. Так что вы должны использовать bitsetэтой структуре данных нужно только немного на число, и у всех современных языков есть реализация. Идея в том, что вы просто помните, был ли номер уже виден:

void print_twice_seen (Iterator &it)//iterates through all numbers
{
  std::bitset< (1L<<32) > seen;//bitset for 2^32 elements, assume 64bit system

  while(it.hasNext()){
       unsigned int val=it.next();//return current element and move the iterator
       if(seen[val])
           std::cout<<"Seen at least twice: "<<val<<std::endl;
       else
           seen.set(val, true);//remember as seen
  }
}