На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Объединение нескольких отсортированных массивов, , с сохранением порядка сортировки при изменении критерия сортировки.
    Есть до 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)];

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

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

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

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


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

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

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

          более чем разумно.
            У меня получился вот такой алгоритм обработки (код на Rust):

            ExpandedWrap disabled
              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);
              }

            Выводит:

            ExpandedWrap disabled
              [[2, 8], [6, 7], [1, 5], [3, 4], [5, 3], [4, 1]]

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

            Добавлено
            ЗЗЫ: Пока писал - уже все разжевали буквами :)
              amk, Akina, JoeUser, интересное решение, правда в моём случае первое число это массив до 256 чисел, что-то вроде уникальных (в рамках каждого массива) данных (образов), численность (частоту) которых пытаюсь подсчитать. Стоит в таком случае предварительно сортировать по данным (образу) или данные сначала пронумеровать и положить в отдельный массив, а сортировать уже пары номер-численность?
              Сообщение отредактировано: FateFlex -
                Цитата FateFlex @
                предварительно сортировать

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

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

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

                  ExpandedWrap disabled
                    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)
                  Сообщение отредактировано: Akina -
                    Akina, массив из 256 байт теоретически имеет 256^256 вариантов заполнения, не представляется возможным столько памяти не то что выделить, а даже купить :jokingly: а для небольших значений конечно было бы очень быстро.
                      FateFlex, приведи более-менее близкий к ситуации пример данных. Пусть вместо 256 значений будет 3.
                        Цитата FateFlex @
                        массив из 256 байт теоретически имеет 256^256 вариантов заполнения

                        Это ты не подумал, прежде чем сказать? Перечитай ещё раз, что я написал...
                          Цитата Akina @
                          Т.е. заранее формируешь приёмный буфер, а первый компонент элемента используешь как индекс.

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

                          Вот эту строку не могу понять :wacko:
                            Цитата JoeUser @
                            v.remove(i+1);

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

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

                                ExpandedWrap disabled
                                      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
                                Сообщение отредактировано: MBo -
                                  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)];

                                  Первые части элементов (массивы в фигурных скобках) уникальны для всех массивов.
                                  Сообщение отредактировано: FateFlex -
                                    Тогда чем-то вроде std::map можно воспользоваться

                                    Добавлено
                                    А, хотя всё равно же придётся сортировать по второму элементу. Не, проще сделать так, как предложил amk. Разве что вместо массивов их хеши хранить в качестве первого элемента.
                                      FateFlex, да OpenGL прав. Массивы в фигурных скобках - это, считай ключи. Таким образом:

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

                                      ЗЫ: Хотя можно поступить и немного иначе на п.4 - вытащить ключи в массив, их отсортировать. И по ним уже отсортированным вывести пары.
                                        Хотя всё зависит от того, на чём и как пишешь. В rust-е, код на котором предоставил JoeUser, лишних кипирований векторов у тебя не будет, если писать как-то так:
                                        ExpandedWrap disabled
                                          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 можешь спокойно подставить массив чисел.
                                          Цитата 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

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

                                            Добавлено
                                            OpenGL, Visual C 2010 без include'ов.
                                              Цитата
                                              если первое не число, а вложенный массив из 256 чисел


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

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

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

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


                                                    Рейтинг@Mail.ru
                                                    [ Script execution time: 0,0590 ]   [ 16 queries used ]   [ Generated: 19.03.24, 03:48 GMT ]