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

          более чем разумно.
          Есть претензии ко мне как к модератору? читайте Правила, разделы 5 и 6, и действуйте соответственно.
          Есть претензии ко мне как к участнику? да ради бога.
          Не нравятся мои ответы? не читайте их.
          В общем, берегите себя. Нервные клетки не восстанавливаются.
            У меня получился вот такой алгоритм обработки (код на 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:

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

                Если концептуально - предварительная сортировка нужна лишь для того, чтобы избавится от многократного поиска. Это позволит использовать один проход при обработке результирующего вектора, не делая вложенных циклов.
                Мои программные ништякиhttp://majestio.info
                  Цитата 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 -
                  Есть претензии ко мне как к модератору? читайте Правила, разделы 5 и 6, и действуйте соответственно.
                  Есть претензии ко мне как к участнику? да ради бога.
                  Не нравятся мои ответы? не читайте их.
                  В общем, берегите себя. Нервные клетки не восстанавливаются.
                    Akina, массив из 256 байт теоретически имеет 256^256 вариантов заполнения, не представляется возможным столько памяти не то что выделить, а даже купить :jokingly: а для небольших значений конечно было бы очень быстро.
                      FateFlex, приведи более-менее близкий к ситуации пример данных. Пусть вместо 256 значений будет 3.
                      Мои программные ништякиhttp://majestio.info
                        Цитата FateFlex @
                        массив из 256 байт теоретически имеет 256^256 вариантов заполнения

                        Это ты не подумал, прежде чем сказать? Перечитай ещё раз, что я написал...
                        Есть претензии ко мне как к модератору? читайте Правила, разделы 5 и 6, и действуйте соответственно.
                        Есть претензии ко мне как к участнику? да ради бога.
                        Не нравятся мои ответы? не читайте их.
                        В общем, берегите себя. Нервные клетки не восстанавливаются.
                          Цитата 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 же сдвинет все элементы. Это долго :)

                              Понятное дело.
                              Чтобы сделать быстрее - можно завести еще один вектор, и вот уже в него вставлять готовые результаты. А в обрабатываемом векторе гонять два указателя и читать "пары", ничего там не удаляя.
                              Мои программные ништякиhttp://majestio.info
                                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 -
                                1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script Execution time: 0,1245 ]   [ 14 queries used ]   [ Generated: 22.09.18, 01:26 GMT ]