Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.128.199.162] |
|
Страницы: (2) 1 [2] все ( Перейти к последнему сообщению ) |
Сообщ.
#16
,
|
|
|
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)]; Первые части элементов (массивы в фигурных скобках) уникальны для всех массивов. |
Сообщ.
#17
,
|
|
|
Тогда чем-то вроде std::map можно воспользоваться
Добавлено А, хотя всё равно же придётся сортировать по второму элементу. Не, проще сделать так, как предложил amk. Разве что вместо массивов их хеши хранить в качестве первого элемента. |
Сообщ.
#18
,
|
|
|
FateFlex, да OpenGL прав. Массивы в фигурных скобках - это, считай ключи. Таким образом:
1) Создаешь ассоциативный массив 2) Пробегаешь по всем векторам и парам в них 3) При итерации для каждой пары увеличиваешь значение по текущему ключу в ассоциативном массиве 4) Далее ассоциативный массив перегоняешь в несортированный Z 5) Z сортируешь по 2-му значению ЗЫ: Хотя можно поступить и немного иначе на п.4 - вытащить ключи в массив, их отсортировать. И по ним уже отсортированным вывести пары. |
Сообщ.
#19
,
|
|
|
Хотя всё зависит от того, на чём и как пишешь. В rust-е, код на котором предоставил JoeUser, лишних кипирований векторов у тебя не будет, если писать как-то так:
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 можешь спокойно подставить массив чисел. |
Сообщ.
#20
,
|
|
|
Цитата 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 Выбрасываем все нулевые элементы. Остаток сортируем по значению. Всё. |
Сообщ.
#21
,
|
|
|
Akina, так и понял, но это для элемента-пары где первое число размером с байт, так гистограмму быстро строить.
В изначально пустом массиве по индексу прибавлять количество - это понятно, но если первое не число, а вложенный массив из 256 чисел, тогда результирующий массив завести не получится >> 2Gb, даже при байтах в качестве элементов результирующего массива. Добавлено OpenGL, Visual C 2010 без include'ов. |
Сообщ.
#22
,
|
|
|
Цитата если первое не число, а вложенный массив из 256 чисел Тогда этот подход реализуется с HashMap/словарём (TDictionary) Однако при таких длинных ключах может быть быстрее отсортировать по ключу (большинство сравнений при сортировке будут задействовать лишь небольшую часть ключа) - в общем, как в первом же ответе предложили. |
Сообщ.
#23
,
|
|
|
Цитата FateFlex @ но если первое не число, а вложенный массив из 256 чисел Ну тады для ускорения обработки возьми его хэш, достаточный для обеспечения вероятности коллизии что-нибудь менее 10-5 (а хоть бы и CRC16 - уже достаточно). Не массивы же ж сравнивать, право слово... но при равенстве хэша сравнение оригинального массива - обязательно. |
Сообщ.
#24
,
|
|
|
Цитата FateFlex @ OpenGL, Visual C 2010 без include'ов. С или С++? И что значит "без include`ов"? Стандартные не в счёт? Если С++, то переписать мой код несложно. Вместо hash_map можно взять тупо std::map (его аналог это unordered_map, но я не помню, есть ли он в 2010 студии). Тело двойного цикла трансформируется тупо в buf[y.key] += y.value; Сортировка есть из коробки в любом порядке. |
Сообщ.
#25
,
|
|
|
OpenGL. вообще ничего не подключаю, просто source.cpp и в нём ни одного inlude.
Значительно быстрее стало работать если сначала по массивам-ключам отсортировать, по ощущениям раз в 5. Думаю пока этого хватит. Всем спасибо. |