21 Востаннє редагувалося wander (16.12.2019 19:46:04)

Re: Порівняти числа, і видати найбільше.

Погоджуюсь з паном Коалою, для того, щоб обрати максимально ефективний підхід потрібно робити заміри. Бо ця ефективність може багато від чого залежати, як я вже сказав, сервер може не підтримувати багатоканал, тоді в багатопотоковій обробці сенсу мало. Також в залежності від даних, навіть при такій підтримці від сервера, всеодно, в багатопотоковості сенсу може не бути, наприклад скачування файлу з ftp-сервера. Далі, також є залежність від фізичної пропускної здатності, тобто ширини каналу (фізичної), а ще, тре дивитися наскільки дані зав’язані одні на одних, можливо при інтенсивному багатопотоку не вийде виграти замітно відносно однопотоку, через необхідність купи синхронізацій..
Взагалом, як я і сказав, треба тестувати і не абстрактно, а реально.

Далі, як пан koala і сказав, тут можна обійтись без масиву. До чого тут scalable-код? А пес срав..

22

Re: Порівняти числа, і видати найбільше.

ur_naz написав:

от вам ще ввідні:
є два сервера з яких треба взяти 10^9 цілих і скласти і відправити на третій сервер. Відомо що обидва сервери мають різні швидкості передачі даних, причому поточна швидкість кожного змінюється випадково. треба скласти алгорітм, що мінімізує витрати часу.
Завдання підвищеного рівня: сервери видають дані хаотично, але у вигляди пари число,індекс

Кожного разу будете нові симптоми вигадувати?

То покажіть своє рішення.

23

Re: Порівняти числа, і видати найбільше.

це ж вам воно припекло?
рішення дуже просте - використати контейнер. якщо пам'яті достатньо, то можна виділити масив, якщо пам'ять обмежена, можна використати map. Це набагато швидше ніж чекати відповідну пару, щоб скласти її

24

Re: Порівняти числа, і видати найбільше.

ur_naz написав:

якщо пам'яті достатньо, то можна виділити масив, якщо пам'ять обмежена, можна використати map

Ну так, а те, що map витрачає більше пам'яті за масив - то дрібниці.
Утім, у вашій умові сказано скласти, а від зміни місць додатків сума не змінюється, отже, номери можна просто викинути, а решту скласти в будь-якій послідовності. І знову масив не потрібен. Формулюйте обережніше :)

Подякували: wander, leofun01, Arete3

25

Re: Порівняти числа, і видати найбільше.

Ну так, а те, що map витрачає більше пам'яті за масив - то дрібниці.

Чого це? масив віджере одразу всю пам'ять,  мапа - в залежності від вхідних потоків.  якщо пара утворилася її можна відправити на потік і видалити з мапи.
СКЛАСТИ ПОПАРНО!!! Ну невже я дав би таке просте завдання??? З одного сервера приходить А0,А1,А2...Аn, з іншого - В0,В1,В2...Вn. Обчислити і відправити на третій сервер А0+В0,А1+В1,А2+В2...Аn+Вn. При чому порядок отримання чисел випадковий, може прилетіти А5, В99999, В755, А1...

26 Востаннє редагувалося P.Y. (17.12.2019 06:32:15)

Re: Порівняти числа, і видати найбільше.

Слухайте, яка масштабованість? Кількість видів тварин, що досі не вимерли, продовжує скорочуватись, ліси вирубуються, океани всі всуціль у пластику... А якщо цю студентську програму візьмуть на озброєння зоомагазини й почнуть заробляти терабайти доларів на поневолених звірятках?.. Ви б туди хоч дорвей вставили, чи що...
https://www.youtube.com/watch?v=VYk4cC65548

27 Востаннє редагувалося koala (17.12.2019 11:50:53)

Re: Порівняти числа, і видати найбільше.

Чого це? масив віджере одразу всю пам'ять,  мапа — в залежності від вхідних потоків.  якщо пара утворилася її можна відправити на потік і видалити з мапи.

Ой! А ми тут суттєво потрапляємо в залежність від організації мапи та хаотичності потоків.
Вважатимемо, що ефективність пошуку та час на виділення пам'яті нас не цікавить, затримки мережі більші, ок.
Будь-яка мапа зберігає пару (ключ, значення). Оскільки в задачі й те, і інше — числа, вважатимемо, що одного розміру. І ще мапа мусить тримати певну кількість додаткових структур (якщо це дерево — то посилання, якщо геш-таблиця — то вільні комірки (заповненість на 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 як масив можна використати бінарний файл з перемоткою на потрібну позицію.
Втім, можете гордо заявити, що ви мали на увазі, що масив - то геш-таблиця із тотожною геш-функцією.

Подякували: wander, Arete2

28

Re: Порівняти числа, і видати найбільше.

ur_naz написав:

Ну так, а те, що map витрачає більше пам'яті за масив - то дрібниці.

Чого це? масив віджере одразу всю пам'ять,  мапа - в залежності від вхідних потоків.  якщо пара утворилася її можна відправити на потік і видалити з мапи.

Наркоман? Чи мазохіст?