Чого це? масив віджере одразу всю пам'ять, мапа — в залежності від вхідних потоків. якщо пара утворилася її можна відправити на потік і видалити з мапи.
Ой! А ми тут суттєво потрапляємо в залежність від організації мапи та хаотичності потоків.
Вважатимемо, що ефективність пошуку та час на виділення пам'яті нас не цікавить, затримки мережі більші, ок.
Будь-яка мапа зберігає пару (ключ, значення). Оскільки в задачі й те, і інше — числа, вважатимемо, що одного розміру. І ще мапа мусить тримати певну кількість додаткових структур (якщо це дерево — то посилання, якщо геш-таблиця — то вільні комірки (заповненість на 90% - вже погано, можна отримати суттєвий час вставлення) та, можливо, таблиці колізій (хоча колізії можуть зберігатися і в основній таблиці за певними правилами). Тобто мапа вимагає від ~2.5n до 4n пам'яті, де n - максимальна кількість невідправлених елементів. Масив виділяється один раз і вимагає n пам'яті.
Наступне питання — скільки нам знадобиться цієї пам'яті; і тут треба уважніше розглянути хаотичність передачі. Якщо джерело хаотичності — помилки та затримки при передаванні, то, швидше за все, це не виллється в потребі більш ніж кілька десятків одиниць пам'яті, це можна суттєво не розглядати для великих n; більше значення матиме різниця у швидкості — в гіршому разі можемо отримати весь масив з одного сервера і ще не почати отримувати з другого, і тут масив однозначно кращий; якщо ж візьмемо навмання, що різниця у швидкостях не перевищуватиме q об'єму (0<q<1), то матимемо в ситуації з масивом витрати в n пам'яті (нам же все по номерах треба зберігати), а для мапи - 2.5qn/3..4qn/3, тобто економія для геш-таблиці складатиме (1-2.5q)n. Для q=1/3 це менше ніж третина n.
Гаразд, а як бути, коли хаотичність не вимушена, а викликана особливостями протоколу, схожого на bittorrent, і номер наступного пакета обирається навмання, рівномірно? Тоді, якщо перший сервер переслав p1, а другий p2 даних (0≤p1,p2≤1), то матимемо p1*p2 збігів та 1-p1-p2+2*p1*p2 унікальних значень. Наприклад, при p1=p2=1/2 нам знадобиться (1-1/2-1/2+2*1/2*1/2)n=1/2n одиниць зберігання, що явно краще для масиву, ніж для мапи.
Таким чином, мапа має сенс лише при незначних хаотичності та різниці у швидкостях. Але навіть тоді при невеликому розмірі мапа, з урахуванням оптимізацій сучасного процесора (кеш і т.д.), може програвати у швидкості масиву пар - час на обчислення всіх переходів чи функцій може виявитися більшим за час перебору двох десятків значень. Хоча, звісно, тут це суттєвого значення не має. А при суттєвій хаотичності чи різниці у швидкості, оскільки витрати пам'яті у будь-якому разі будуть O(n), масив значно виграє як за розміром, так і за утилізацією процесора. При великих значеннях n як масив можна використати бінарний файл з перемоткою на потрібну позицію.
Втім, можете гордо заявити, що ви мали на увазі, що масив - то геш-таблиця із тотожною геш-функцією.
