Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.226.96.37] |
|
Страницы: (2) [1] 2 все ( Перейти к последнему сообщению ) |
Сообщ.
#1
,
|
|
|
Есть до 256 массивов содержащих до 65536 пар чисел.
Массивы отсортированы по второму числу в порядке убывания. A = [(1, 5), (2, 3), (3, 1)]; B = [(5, 3), (3, 2), (4, 1)]; C = [(6, 7), (2, 5), (3, 1)]; Требуется объединить массивы складывая вторые числа при совпадении первых и сохраняя порядок сортировки. Z = [(2, 8), (6, 7), (1, 5), (3, 4), (5, 3), (4, 1)]; Сортировку слиянием в чистом виде применить нельзя, так как идёт слияние и критерий сортировки меняется (второе число может увеличиться и стать больше предыдущих). Беру из массивов пары с большим вторым числом и пробегаю по результирующему массиву с уже добавленными парами, а затем делаю быструю сортировку результирующего массива, но это долго. Может есть какой-то более быстрый готовый велосипед? |
Сообщ.
#2
,
|
|
|
Цитата FateFlex @ Сортировку слиянием в чистом виде применить нельзя, так как идёт слияние и критерий сортировки меняется (второе число может увеличиться и стать больше предыдущих). Беру из массивов пары с большим вторым числом и пробегаю по результирующему массиву с уже добавленными парами, а затем делаю быструю сортировку результирующего массива, но это долго. Получается, что у тебя на каждом шаге итоговый массив может быть сильно пересортирован. Но при этом перемещаться по массиву будет только один элемент. Кстати, быстрая сортировка не сохраняет порядок. Если бы не требование сохранять порядок, то лучшим выбором было бы отсортировать по первому элементу, объединить совпадающие по первому элементу записи, и потом отсортировать по второму элементу (сумме) |
Сообщ.
#3
,
|
|
|
Что в данном случае означает "с сохранением порядка сортировки"?
|
Сообщ.
#4
,
|
|
|
Цитата FateFlex @ и сохраняя порядок сортировки На текущей постановке задачи термин в принципе не имеет смысла и должен быть трансформирован в нечто вроде "итоговый массив должен быть отсортирован по второму элементу". И сразу становится понятно, что предложение Цитата amk @ отсортировать по первому элементу, объединить совпадающие по первому элементу записи, и потом отсортировать по второму элементу (сумме) более чем разумно. |
Сообщ.
#5
,
|
|
|
У меня получился вот такой алгоритм обработки (код на Rust):
fn main() { // объявляем вектор векторов массивов двух элементов let m = vec![ vec![[1, 5], [2, 3], [3, 1]], vec![[5, 3], [3, 2], [4, 1]], vec![[6, 7], [2, 5], [3, 1]] ]; // делаем одномерный вектор из всех массивов двух элементов let mut v: Vec<[i32;2]> = vec![]; for x in m { for y in x { v.push(y); } } // сортируем вектор массивов по ключу, равному первому элементу массивов v.sort_by(|&a, &b| a[0].cmp(&b[0])); // производим "сложения" смежных массивов, если их первый элемент равен let mut i = 0; loop { if i+1 < v.len() { if v[i][0] == v[i+1][0] { v[i][1] += v[i+1][1]; v.remove(i+1); } else { i+=1; } } else { break; } } // сортируем по убыванию вектор массивов по ключу, равному второму элементу массивов v.sort_by(|&a, &b| b[1].cmp(&a[1])); // выводим результат println!("{:?}", v); } Выводит: [[2, 8], [6, 7], [1, 5], [3, 4], [5, 3], [4, 1]] ЗЫ: Если набыдлокодил малеха - сорри, это моя вторая программа на Rust после "Hello world!" Добавлено ЗЗЫ: Пока писал - уже все разжевали буквами |
Сообщ.
#6
,
|
|
|
amk, Akina, JoeUser, интересное решение, правда в моём случае первое число это массив до 256 чисел, что-то вроде уникальных (в рамках каждого массива) данных (образов), численность (частоту) которых пытаюсь подсчитать. Стоит в таком случае предварительно сортировать по данным (образу) или данные сначала пронумеровать и положить в отдельный массив, а сортировать уже пары номер-численность?
|
Сообщ.
#7
,
|
|
|
Цитата FateFlex @ предварительно сортировать Если концептуально - предварительная сортировка нужна лишь для того, чтобы избавится от многократного поиска. Это позволит использовать один проход при обработке результирующего вектора, не делая вложенных циклов. |
Сообщ.
#8
,
|
|
|
Цитата FateFlex @ в моём случае первое число это массив до 256 чисел Если набор известен и ограничен - используй подсчёт с последующей чисткой и сортировкой результата. Т.е. заранее формируешь приёмный буфер, а первый компонент элемента используешь как индекс. В псевдокоде на VB это будет приблизительно так: Dim Result.Component(1 To 256) ' Накопление результата For Each OneArray In ArrayOfArrays For Each OneElement In OneArray Result.Component(OneElement.Component(1)) = Result.Component(OneElement.Component(1)) + OneElement.Component(2) Next OneElement Next OneArray ' Удаление пустых элементов For Each OneElement In Result If OneElement.Component(1) = 0 Then Result.Remove OneElement Next OneElement ' Сортировка Result.Sort(Component(2) DESC) |
Сообщ.
#9
,
|
|
|
Akina, массив из 256 байт теоретически имеет 256^256 вариантов заполнения, не представляется возможным столько памяти не то что выделить, а даже купить а для небольших значений конечно было бы очень быстро.
|
Сообщ.
#10
,
|
|
|
FateFlex, приведи более-менее близкий к ситуации пример данных. Пусть вместо 256 значений будет 3.
|
Сообщ.
#11
,
|
|
|
Цитата FateFlex @ массив из 256 байт теоретически имеет 256^256 вариантов заполнения Это ты не подумал, прежде чем сказать? Перечитай ещё раз, что я написал... |
Сообщ.
#12
,
|
|
|
Цитата Akina @ Т.е. заранее формируешь приёмный буфер, а первый компонент элемента используешь как индекс. Не понял как это заранее сформировать буфер... память выделить под массив? Первый компонент элемента, это и есть массив из 256 байт? Цитата Akina @ Result.Component(OneElement.Component(1)) = Result.Component(OneElement.Component(1)) + OneElement.Component(2) Вот эту строку не могу понять |
Сообщ.
#13
,
|
|
|
Цитата JoeUser @ v.remove(i+1); remove же сдвинет все элементы. Это долго |
Сообщ.
#14
,
|
|
|
Цитата OpenGL @ remove же сдвинет все элементы. Это долго Понятное дело. Чтобы сделать быстрее - можно завести еще один вектор, и вот уже в него вставлять готовые результаты. А в обрабатываемом векторе гонять два указателя и читать "пары", ничего там не удаляя. |
Сообщ.
#15
,
|
|
|
FateFlex возможно, тебе может помочь что-то подобное:
Histogram: array[0..255] of TPoint; for i := 0 to 255 do begin Histogram[i].X := i; Histogram[i].Y := 0; end; for i := 0 to ArrayCnt - 1 do for j := 0 to A[i].Length - 1 do Inc(Histogram[A[i, j].First].Y, A[i, j].Second); Sort Histogram by Y key |