На главную
ПРАВИЛА 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,1511 ]   [ 19 queries used ]   [ Generated: 20.06.18, 05:34 GMT ]