Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум на Исходниках.RU > Алгоритмы > Объединение нескольких отсортированных массивов,


Автор: FateFlex 13.06.18, 20:43
Есть до 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)];

Сортировку слиянием в чистом виде применить нельзя, так как идёт слияние и критерий сортировки меняется (второе число может увеличиться и стать больше предыдущих).

Беру из массивов пары с большим вторым числом и пробегаю по результирующему массиву с уже добавленными парами, а затем делаю быструю сортировку результирующего массива, но это долго.

Может есть какой-то более быстрый готовый велосипед?

Автор: amk 13.06.18, 23:38
Цитата FateFlex @
Сортировку слиянием в чистом виде применить нельзя, так как идёт слияние и критерий сортировки меняется (второе число может увеличиться и стать больше предыдущих).

Беру из массивов пары с большим вторым числом и пробегаю по результирующему массиву с уже добавленными парами, а затем делаю быструю сортировку результирующего массива, но это долго.


Получается, что у тебя на каждом шаге итоговый массив может быть сильно пересортирован. Но при этом перемещаться по массиву будет только один элемент.
Кстати, быстрая сортировка не сохраняет порядок.

Если бы не требование сохранять порядок, то лучшим выбором было бы отсортировать по первому элементу, объединить совпадающие по первому элементу записи, и потом отсортировать по второму элементу (сумме)

Автор: MBo 14.06.18, 03:44
Что в данном случае означает "с сохранением порядка сортировки"?

Автор: Akina 14.06.18, 04:14
Цитата FateFlex @
и сохраняя порядок сортировки

На текущей постановке задачи термин в принципе не имеет смысла и должен быть трансформирован в нечто вроде "итоговый массив должен быть отсортирован по второму элементу". И сразу становится понятно, что предложение
Цитата amk @
отсортировать по первому элементу, объединить совпадающие по первому элементу записи, и потом отсортировать по второму элементу (сумме)

более чем разумно.

Автор: JoeUser 14.06.18, 05:08
У меня получился вот такой алгоритм обработки (код на Rust):

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    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);
    }

Выводит:

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    [[2, 8], [6, 7], [1, 5], [3, 4], [5, 3], [4, 1]]

ЗЫ: Если набыдлокодил малеха - сорри, это моя вторая программа на Rust после "Hello world!" :lol:

Добавлено
ЗЗЫ: Пока писал - уже все разжевали буквами :)

Автор: FateFlex 14.06.18, 05:46
amk, Akina, JoeUser, интересное решение, правда в моём случае первое число это массив до 256 чисел, что-то вроде уникальных (в рамках каждого массива) данных (образов), численность (частоту) которых пытаюсь подсчитать. Стоит в таком случае предварительно сортировать по данным (образу) или данные сначала пронумеровать и положить в отдельный массив, а сортировать уже пары номер-численность?

Автор: JoeUser 14.06.18, 06:17
Цитата FateFlex @
предварительно сортировать

Если концептуально - предварительная сортировка нужна лишь для того, чтобы избавится от многократного поиска. Это позволит использовать один проход при обработке результирующего вектора, не делая вложенных циклов.

Автор: Akina 14.06.18, 06:19
Цитата FateFlex @
в моём случае первое число это массив до 256 чисел

Если набор известен и ограничен - используй подсчёт с последующей чисткой и сортировкой результата. Т.е. заранее формируешь приёмный буфер, а первый компонент элемента используешь как индекс.

В псевдокоде на VB это будет приблизительно так:

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    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)

Автор: FateFlex 14.06.18, 06:43
Akina, массив из 256 байт теоретически имеет 256^256 вариантов заполнения, не представляется возможным столько памяти не то что выделить, а даже купить :jokingly: а для небольших значений конечно было бы очень быстро.

Автор: JoeUser 14.06.18, 06:48
FateFlex, приведи более-менее близкий к ситуации пример данных. Пусть вместо 256 значений будет 3.

Автор: Akina 14.06.18, 06:48
Цитата FateFlex @
массив из 256 байт теоретически имеет 256^256 вариантов заполнения

Это ты не подумал, прежде чем сказать? Перечитай ещё раз, что я написал...

Автор: FateFlex 14.06.18, 07:20
Цитата Akina @
Т.е. заранее формируешь приёмный буфер, а первый компонент элемента используешь как индекс.

Не понял как это заранее сформировать буфер... память выделить под массив?
Первый компонент элемента, это и есть массив из 256 байт?
Цитата Akina @
Result.Component(OneElement.Component(1)) = Result.Component(OneElement.Component(1)) + OneElement.Component(2)

Вот эту строку не могу понять :wacko:

Автор: OpenGL 14.06.18, 07:28
Цитата JoeUser @
v.remove(i+1);

remove же сдвинет все элементы. Это долго :)

Автор: JoeUser 14.06.18, 08:00
Цитата OpenGL @
remove же сдвинет все элементы. Это долго :)

Понятное дело.
Чтобы сделать быстрее - можно завести еще один вектор, и вот уже в него вставлять готовые результаты. А в обрабатываемом векторе гонять два указателя и читать "пары", ничего там не удаляя.

Автор: MBo 14.06.18, 08:10
FateFlex возможно, тебе может помочь что-то подобное:

<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
        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

Автор: FateFlex 14.06.18, 08:11
JoeUser, пусть в нашем байте будет всего 2 бита.
Есть 3 массива с элементами-парами, представим массивом массивов.
Первая часть элемента-пары это массив длиной 4 элемента, каждый из которых может принимать 4 значения 0..3.
Вторя часть элемента-пары это количество встретившихся вариантов заполнения первой части (массива в фигурных скобках).
Массивы отсортированы по второму числу, то есть по количеству.

A = [({1, 1, 1, 1}, 5), ({2, 2, 2, 2}, 3), ({3, 3, 3, 3}, 1)];
B = [({0, 0, 1, 1}, 3), ({3, 3, 3, 3}, 2), ({0, 0, 1, 0}, 1)];
C = [({0, 0, 1, 2}, 7), ({2, 2, 2, 2}, 5), ({3, 3, 3, 3}, 1)];

Требуется объединить массивы и отсортировать по количеству.

Z = [({2, 2, 2, 2}, 8), ({0, 0, 1, 2}, 7), ({1, 1, 1, 1}, 5), ({3, 3, 3, 3}, 4), ({0, 0, 1, 1}, 3), ({0, 0, 1, 0}, 1)];

Первые части элементов (массивы в фигурных скобках) уникальны для всех массивов.

Автор: OpenGL 14.06.18, 08:19
Тогда чем-то вроде std::map можно воспользоваться

Добавлено
А, хотя всё равно же придётся сортировать по второму элементу. Не, проще сделать так, как предложил amk. Разве что вместо массивов их хеши хранить в качестве первого элемента.

Автор: JoeUser 14.06.18, 08:37
FateFlex, да OpenGL прав. Массивы в фигурных скобках - это, считай ключи. Таким образом:

1) Создаешь ассоциативный массив
2) Пробегаешь по всем векторам и парам в них
3) При итерации для каждой пары увеличиваешь значение по текущему ключу в ассоциативном массиве
4) Далее ассоциативный массив перегоняешь в несортированный Z
5) Z сортируешь по 2-му значению

ЗЫ: Хотя можно поступить и немного иначе на п.4 - вытащить ключи в массив, их отсортировать. И по ним уже отсортированным вывести пары.

Автор: OpenGL 14.06.18, 08:44
Хотя всё зависит от того, на чём и как пишешь. В rust-е, код на котором предоставил JoeUser, лишних кипирований векторов у тебя не будет, если писать как-то так:
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    mod engine;
    use std::collections::HashMap;
     
    fn smart_merge<T: Clone + std::cmp::Eq + std::hash::Hash>(v: &Vec<Vec<(T, i32)>>) -> Vec<(T, i32)>
    {
        let mut buf = HashMap::new();
     
        for x in v
        {
            for y in x
            {
                let q = buf.entry(&y.0).or_insert(0);
                
                *q += y.1;
            }
        }
     
        let mut res = Vec::new();
        for (key, value) in buf
        {
            res.push((key.clone(), value));
        }
        res.sort_by(|a, b|{a.1.cmp(&b.1).reverse()});
     
        res
    }
     
    fn main()
    {
        let v = vec![
            vec![(1, 5), (2, 3), (3, 1)],
            vec![(5, 3), (3, 2), (4, 1)],
            vec![(6, 7), (2, 5), (3, 1)]
        ];
     
        let res = smart_merge(&v);
        println!("{:?}", res);
    }


Добавлено
Поскольку код в данном случае обобщённый - вместо T можешь спокойно подставить массив чисел.

Автор: Akina 14.06.18, 09:40
Цитата FateFlex @
Вот эту строку не могу понять

:facepalm:

Цитата FateFlex @
A = [(1, 5), (2, 3), (3, 1)];
B = [(5, 3), (3, 2), (4, 1)];
C = [(6, 7), (2, 5), (3, 1)];

Создаём массив из 256 элементов, все нули. Ну пусть Result(256).

Берём первый элемент первого массива. Это A(1) = (1,5). Соответственно Result(1) = Result(1) + 5 = 5.
Берём второй элемент первого массива. Это A(2) = (2,3). Соответственно Result(2) = Result(2) + 3 = 3.
Берём третий элемент первого массива. Это A(3) = (3,1). Соответственно Result(3) = Result(3) + 1 = 1.
Берём первый элемент второго массива. Это B(1) = (5,3). Соответственно Result(5) = Result(5) + 3 = 3.
Берём второй элемент второго массива. Это B(2) = (3,2). Соответственно Result(3) = Result(3) + 2 = 3.
...
Берём третий элемент третьего массива. Это C(3) = (3,1). Соответственно Result(3) = Result(3) + 1 = 4.

Итого:

Result(1)=5
Result(2)=8
Result(3)=4
Result(4)=1
Result(5)=3
Result(6)=7
Result(7)=0
Result(8)=0
...
Result(256)=0

Выбрасываем все нулевые элементы. Остаток сортируем по значению. Всё.

Автор: FateFlex 14.06.18, 10:11
Akina, так и понял, но это для элемента-пары где первое число размером с байт, так гистограмму быстро строить.
В изначально пустом массиве по индексу прибавлять количество - это понятно, но если первое не число, а вложенный массив из 256 чисел, тогда результирующий массив завести не получится >> 2Gb, даже при байтах в качестве элементов результирующего массива.

Добавлено
OpenGL, Visual C 2010 без include'ов.

Автор: MBo 14.06.18, 10:17
Цитата
если первое не число, а вложенный массив из 256 чисел


Тогда этот подход реализуется с HashMap/словарём (TDictionary)

Однако при таких длинных ключах может быть быстрее отсортировать по ключу (большинство сравнений при сортировке будут задействовать лишь небольшую часть ключа) - в общем, как в первом же ответе предложили.

Автор: Akina 14.06.18, 10:43
Цитата FateFlex @
но если первое не число, а вложенный массив из 256 чисел

Ну тады для ускорения обработки возьми его хэш, достаточный для обеспечения вероятности коллизии что-нибудь менее 10-5 (а хоть бы и CRC16 - уже достаточно). Не массивы же ж сравнивать, право слово... но при равенстве хэша сравнение оригинального массива - обязательно.

Автор: OpenGL 14.06.18, 10:54
Цитата FateFlex @
OpenGL, Visual C 2010 без include'ов.

С или С++? И что значит "без include`ов"? Стандартные не в счёт?
Если С++, то переписать мой код несложно. Вместо hash_map можно взять тупо std::map (его аналог это unordered_map, но я не помню, есть ли он в 2010 студии). Тело двойного цикла трансформируется тупо в buf[y.key] += y.value; Сортировка есть из коробки в любом порядке.

Автор: FateFlex 18.06.18, 12:53
OpenGL. вообще ничего не подключаю, просто source.cpp и в нём ни одного inlude.
Значительно быстрее стало работать если сначала по массивам-ключам отсортировать, по ощущениям раз в 5.
Думаю пока этого хватит.
Всем спасибо.
:lol:

Powered by Invision Power Board (https://www.invisionboard.com)
© Invision Power Services (https://www.invisionpower.com)