Итак мамкины погромисты. Есть n отсортированных массивов 32-битных интов, достаточно большого размера. Как их наиболее эффективно слить в один отсортированный массив, используя по возможности O(1) памяти, приоритет в скорости работы алгоритма. Жду ваших решений. Язык С++.
>>823606 (OP)>достаточно большого размераДостаточно для чего?
>>823622Достаточно для того чтобы пхп-обезьяным, которые переспрашивают элементарные COMPUTER SCIENCE вещи, шли мимо.
>>823606 (OP)Сливай как есть и потом сортируй
Почему-то только петушиной (chiken) схеме есть foldr из коробки.https://ideone.com/pMRc78
>>823624Слыш ты потише будь в этой категории.
>>823606 (OP)слушай сюда внимательно. Заводишь массив длинной равный количеству сортируемых массивов умножить на их количество элементов. И чтобы там были одни нулики.Завел? Молодец, сыночек. Теперь берешь каждый элемент из твоих ху-эн массивов и смотришь его значение. Теперь в общем массиве по индексации значения увеличиваешь счетчик, сука на один. Так за один проход ты узнаешь сколько и каких чисел у тебя записано. Осталось развернуть все это говно, для этого делаешь второй проход по общему массиву печатая индекс число раз равное содержимому массива по этому индексу.Соответственно это будет возврастающая сортировка, для убывающей рассматриваешь индексацию относительно конца массива как нулевого элемента.Я бы мог тебе написать алгоритм, но ты выебываешься, поэтому лучше я пошлю тебя на хуй, кек.
Ничего умнее того, чтобы в каком-то порядке все эти массивы склеить, думаю придумать нельзя. Только нужно оптимально выбрать этот порядок: на каждом шаге будем брать два массива с наименьшими из присутствующих размеров и склеивать(функция merge, но в плане O(1) памяти, если это так критично, может найдешь нужный метод здесь http://www.dcs.kcl.ac.uk/technical-reports/papers/TR-04-05.pdf, написать тогда придется естественно самому). Реализовать для наибольшей скорости можно так: пусть мы храним какую-нибудь heap из этих массивов(можно set, но по времени лишний логарифм), в качестве ключа размер массива, в корне элемент с минимальным ключом. На каждом шаге достаем из корня пирамиды элемент, затем второй, склеиваем их и добавляем обратно в пирамиду, и все это продолжаем пока не останется один элемент, который будет результатом.
>>823627>>823625Мы подумаем и вам перезвоним.>>823628> O(1) памяти> Заводишь массив длинной равный количеству сортируемых массивов умножить на их количество элементовМы подумаем и вам перезвоним.
>>823606 (OP)http://pastebin.com/8RKChWHAтолько для 32-бит интов</thread>
>>823632Уноси отсюда свое вырвиглазное говно, ебаный олимпиадник.
Байтоебы с некомпозабельными структурами данных в очередной раз борются с уебищностью своего недоязыка.
>>823633Но если моего вырвиглазного гавна не будет, то ты пойдешь работать на завод с 6 утра, и не будешь говнокодить на пхп........
>>823634:) и попивают кристал на берегу западного побережья
>>823636Потреблядство для быдла, а мне и за ноутом со слакой заебись.
>>823637
>>823606 (OP)>Есть n отсортированных массивов 32-битных интовмассивы read-only или можно модифицировать?
Самый тупой алгоритм даёт O(n) памяти и столько же скорость работы (где n - кол-во элементов во всех массивах). Куда уж эффективней?
>>823630>Мы подумаем и вам перезвоним.ПоХаПе манька даже и не знает, что такое О(1), лул.
>>823606 (OP)Модифицируй сортировку слиянием. /тред
>>823672А вообще ОП даун. Круче метод не придумаешь
Пиздец, чмошу опустили на собеседовании, а он теперь тут пытается чет узнать. Найс трай, алсо любое пхпбыдло будет получше такого чсв скама как ты.
>>823653>>823606 (OP)Минимальная сложность у такого алгоритма будет O(nln(n)) иначе вы решили бы задачу сортировки на O(1)Т.е имея массивы [[17],[11],[47],[23],[0]] вы не сможете создать новый, отсортированный быстрее чем за О(n*ln(n))
>>823704Используя дополнительные данные задачи (там инты 32-битные) можно решить быстрее.
>>823628Ты мне предлагаешь решение за О(n) доп. памяти и среднем временем работы n log n? А теперь представь что у нас 256 массивов по 1гб каждыйдопустим мы все это делаем в памяти, хотя на деле я подгружаю части из этих чанков в массиве равномерно распределенные 32 битные инты, то есть твой алгоритм превращается в говно и работает не лучше других известных мне, а то и хуже.>>823629>>823632>>823672В общем, я пробовал слудующие алгоритмы:- Слияние через очередь с приоритетом- Различные варианты сортировки k слитых массивов в один ( quicksort, merge sort, msd/lsd radix sort, in-place heap sort ) все они дают не достаточную скорость работы и основанны на тупой сортировке уже отсортированных массивов. Хотя распаралеливание merge sort дает чуть лучшие результаты, но требует доп. O(n) памяти.Так же пробовал стандартные std::inplace_merge, и распаралеленные варианты с divide-and-conquer алгоритмом.Все это работает не так быстро как хотелось бы.>>823704Двачую. Но вообще теоритически можно за O(n*log(k)) где k - кол-во массивов, через очередь с приоритетом, дело в том что при больших k операции вставки и удаление в очередь становятся слишком дорогостоищими.
>>823730Может и можно быстрее, но за О(1) по времени отсортировать нельзя, ОП нас наебывает.
>>823741Слияние будет работать за n * Σ, где n - кол-во массивов, а Σ - суммарное кол-во элементов
>>823741Есть K массивов размером N.Сортируем каждый из них за KN log N.Создаём PriorityQueue размером K и заполняем её структурами состоящими из ссылки на массив и текущего указателя в массиве, по которому происходит сравнение структур.Достаём минимальную структуру из PQ, кладём в новый KN массив элемент по указателю из структуры, увеличиваем указатель на 1 и если он не покинул массив, то кладём структуру обратно в PQ.Повторяем до истощения PQ (K^2 N log K)ИТОГО: O(KN(log N + K log K))О(NK log K), если массивы уже отсортированы
>>823753>О(K^2 N log K)fix
А вообще у тебя просто промежуточный этап сортировки слиянием. Ничего круче, чем закончить эту сортировку тем же слиянием не придумаешь. Мое скромное мнение
>>823753Ты читал, что я написал вообще?>Достаём минимальную структуру из PQ>кладём структуру обратно в PQЯ говорю при больших K этот алгоритм уступает банальным сортировкам, потому что аперации удаления/вставки из кучи занимают суммарно слишком много времени.
>>823758>O(log n) performance for inserts and removalsНе шибко-то много я полагаю.
>>823759Асимптотика тут обманчива. На деле, в профайлере, в такой сортировке, такие операции занимают до 50% общего времени сортировки.
>>823760add. при большом кол-ве К.
>>823606 (OP)Битоническое слияние.
>>823760Может ты через жопу реализовал, кто ж тебя знает.Вот тут аналогичный подход использован:http://stackoverflow.com/a/37944473/6112474
>>823744Он просит O(1) по памяти. Правда, решения, опережающие O(n*log(n)) будут прожорливые по памяти очень.
>>823763Я уже думал в эту сторону, попробовать задействовать GPU. Если у нас в оперативной памяти будет дополнительный буффер размером с буффер в памяти GPU, то это подходит по заданным критериям по расходу памяти.>>823764Вот мой http://pastebin.com/4Yg4SFZbВсе просто, Есть класс FileChunk - ck который постепенно подгружает k-файл с отсортированными данными, мы вставляем его в PQ где сравнивается указатель на текущее значение в чанке, и помещается в top наименьшее т.к. у нас min-heap затем это наименьшее вытаскивается из PQ ( что занимает дохуя времени, когда у нас много чанков ) и кладется в буффер, который потом записывается на диск по достижению лимита, затем указатель в чанке инкрементируется на след. значение и почещается обратно в PQ, если мы достигли конца файла и больше данных в чанке нет, мы просто пропускаем шаг вставки обратно в очередь, и вся эта байда длится пока очередь не окажется пустой.
>>823776> Я уже думал в эту сторону, попробовать задействовать GPUСоснёшь 100% с проглотом, сортировка это синоним GPU-непригодного алгоритма. Только если гранты мелкие пилить на публикациях в этом направлении. Не забывай постить в тред отчёты о прогрессе.
>>823606 (OP)external bucket merge sort
>>823703>Пиздец, чмошу опустили на собеседовании, а он теперь тут пытается чет узнать/threadПереходим в тред обсуждения кластеров метапарадигм.
Алгоритмоебы, объясните, почему однопоточный merge sort сортирует 100 000 элементов быстрее, чем многопоточный?49 мс (однопоточный) против 1000 мс (многопоточный)
>>823883Забыл код.https://ideone.com/jALSNb
>>823884Двачую, что у тебя 2 ядра. Тебе доступно 1 и ты НА ОДНОМ ЯДРЕ ПИШИШЬ МНОГОПОТОЧНОСТЬ!!!!!!
>>823884>WINAPI
>>823884Код не изучал, возможно криво реализована синхронизация, либо у тебя потоков намного больше чем вычислительных ядер, что создает задержку на переключение контекста процессора.
>>823898Удали, слышь. Олимпиадники умеют только гавно на паскале писать. Какое переключение контекста. Ты что ИНЖЕНЕР???
>>823606 (OP)Ты забыл указать цену, а вообще можно решить за O(nk), как было сказано выше.
>>823763Хуйня это битоническое слияние, распаралелленая версия с помощью Intel TBB которая загружает все 8 ядер моего i7 4770k, работает в дохуища раз медленнее обычного паралельного merge sort'a. Если и реализовать его, то на GPU.>>823971С меня как всегда нихуя же. Решение за O(nk) это какое именно?
Короче? пока тупая повторная сортировка в лоб с помощью tbb::parallel_sort работает быстрее всех.
>>824084O(nk) - тупо сливать
>>823606 (OP)Что значит O(1) памяти? Где хранить результат?
>>823630сажа скрыл
>>823606 (OP)Ты сначала сравни диапазоны у массивов, сливать надо только те, у которых диапазоны пересекаются. Потому бинарным поиском ищещь с какого по какой элемент делать слияние, их и мерджишь.
Короче решил заюзать SIMD инструкции для параллельного мерджа щас колупаюсь с SSE и AVX.
>>825412> заюзать SIMD у тебя мемори-баунд! у тебя памяти не хватает на всё. какое саймди
Накидайте манов по SIMD мне за щеку, хочу разобраться в этом.
>>825425Так при чем здесь память? Я юзаю 256 битные регисты для мерджа, их так же можно заюзать в in-place алгоритме.
>>825433https://software.intel.com/sites/landingpage/IntrinsicsGuide/
Вообще еще в планах написать сортировку на SIMD, сейчас изучаю сортировочные сети и как их лучше заюзать с SIMD и распаралелить.
Принес первые результаты моего simd мерджа по сравнению с стл.-sequential_simd_merge has finished for 10.4963 sec.-std::merge has finished for 26.8874 sec.То есть, мы получаем х2.6 увелечение производительности по сравнению с стл мерджем. Для начала не плохо, еще есть место для оптимизации и распараллеливания.
>>825457>SIMDПокажи код.
>>823884Что там thread_L в оба _beginthread передается, так и должно?Код не смог запустить, если что. О приведении указателей ругается.
>>823884
>>823741ОП-хуй, если у тебя 256 массивов по 1гб, то решение вот этого господина >>823628 лучшее. Тебе потребуется всего 4гб памяти при условии равномерного распределения чисел.Эта хуйня, кстати элементарно пилится на gpu при наличии достаточного количества памяти.Так же хочу тебе сказать, что ты слишком много выёбываешься для своего уровня знаний.
>>824207Видать оп сразу на винт хочет хуйарить
>>823606 (OP)>>823606 (OP)Для того чтобы просто склеить n массивов в один большой>используя по возможности O(1) памятинадо будет сделать дохуя реаллокейтов, что убьёт производительность.Как ты собираешься решать эту проблему?Скорее всего столкнувшись с этим ты пойдёшь на компромис в плане использования дополнительной памяти, а значит и ограничения на O(1) для сортировки надуманы.Кстати, скажи, ты сильно преувеличивал, когда писал про>А теперь представь что у нас 256 массивов по 1гб каждый?При таких объёмах можно создать массив, в котором будут храниться тупо количества вхождений каждого возможного инта. Я бы сделал массив из 2^32 байтов (4 гб), и мапу для случаев переполнения байтов.Если твои объёмы данных позволяют такое, то ничего эффективнее не придумаешь.
>>823606 (OP)>Есть n отсортированных массивов 32-битных интов>Как их наиболее эффективно слить в один отсортированный массив, Проходишь по первому и последнему элементу каждого массива, сортируешь любой удобной тебе сортировкой, сливаешь. Памяти минимум (если ты не даун, который все массивы будет в память загонять), скорость работы в приоритете. /thread
>>825485Бля, опоздал.
>>823741Не выёбуйся, и делай как написал >>823628.>Ты мне предлагаешь решение за О(n) доп. памятиНет, 4 гб это константа, то есть O(1).>среднем временем работы n log n?Нет, O(n).>в массиве равномерно распределенные 32 битные инты>256 массивов по 1гбИдеальный случай. Значит каждое значение будет встречаться в среднем 16 раз. Отсортированный массив будет выглядеть примерно так:-2147483648, -2147483648, -2147483648, -2147483648, -2147483648, -2147483648, -2147483648, -2147483648, -2147483648, -2147483648, -2147483648, -2147483648, -2147483648, -2147483648, -2147483648, -2147483648, -2147483648, -2147483648, -2147483648, -2147483648, -2147483647, -2147483647, -2147483647, -2147483647, -2147483647, -2147483647, -2147483647, -2147483647, -2147483647, -2147483647, -2147483647, ...
>>823883Всё упирается в пропускную способность оперативки. Даже одного ядра достаточно, чтобы занять весь её канал на такое вычислительно простой операции как сравнение.Добавление других ядер только портит кеш и добавляет нелокальности в обращения к оперативке.
>>823606 (OP)>Осторожно! Алгоритмические задачи.А на деле хуита.
>>825461Merge kernel сливает за пару циклов массив 8х8, использую его в гибридном DAC мердже.http://pastebin.com/CbySfUv3>>825476>всего 4гб памяти>>825495Не на каждой машине есть 4гб лишней памяти, без учета того, что программа еще сама по себе какую-то память использует.>>825485О(1) памяти не значит что не использовать вообще дополнительную память, но 4гб это через чур, как мне предлагали выше с Counting Sort'ом.>>825486Диванные эксперты подъехали. Это был мой самый первый способ слияния, тупой пересортировкой по мелким блокам.В общем-то, написание своего мерджа дало ~20 кратное увеличение производительности, что меня устраивает. Теперь все упирается в disk IO, для подгрузки и записи блоков, а из процессора я выжал максимум. При слияние, на моей машине, загружаются все 8 ядер на 100% + некоторое колдовство над организацией памяти дало нехилый выигрышь.
>>826057>Это был мой самый первый способ слияния,Ах, да, извините, я должен был прочитать ваши мысли и понять это.> тупой пересортировкой по мелким блокам.У тебя в условии уже есть пункт где массивы уже отсортированы. Стало быть тебе всего-то и надо составить в ряд кучку больших массивов.
>>823606 (OP)Так что в итоге то? ОП обосрался?
>>824207Очевидно, имеется в виду, что можно использовать только ту память, что уже занята исходными данными, плюс какой-то константный оверхед.
