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

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

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


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

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

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


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