Язык программирования не указан, сказано только, что была сделана попытка создать алгоритм в Пайтоне, но работа оказалась очень медленной. Это не удивительно, ведь Пайтон - интерпретатор и там уж не до оптимизации.
Предлагаю решение на PascalABC.NET. Приводятся тайминги пяти прогонов, разрешение таймера - 16 мс.
Исходные последовательности: - 1 млн случайных целых из [100;2000]; - 2 млн случайных целых из [50;1500]; - 3 млн случайных целых из [1;1000];
Алгоритм: - генерируем последовательности; - создаем и заполняем для каждой последовательности частотный словарь в виде кортежа <ключ><количество>, где ключ - значение элемента, количество - количество раз, которое этот элемент встретился в последовательности; - создаем последовательности ключей для всех трех словарей и находим их пересечение; - удаляем из каждого словаря элементы, ключей которых нет в пересечении; - создаем на основе каждого словаря последовательность значений (частот) и сортируем её по возрастанию; - для каждой пары значений первой и второй последовательности выбираем минимальное значение, а затем поступаем так же с результирующей и третьей последовательностью, находя в конце сумму её членов.
// PascalABC.NET 3.2, сборка 1374 от 10.01.2017 // Внимание! Если программа не работает, обновите версию!
begin var t0:=Milliseconds; var a1:=ArrRandom(1000000,100,2000); var a2:=ArrRandom(2000000,50,1500); var a3:=ArrRandom(3000000,1,1000); var t1:=MillisecondsDelta; Writeln('Инициализация: ',t1,' мс'); MillisecondsDelta;
var d1:=new Dictionary<integer,integer>; foreach var e in a1 do d1[e]:=d1.Get(e)+1; var d2:=new Dictionary<integer,integer>; foreach var e in a2 do d2[e]:=d2.Get(e)+1; var d3:=new Dictionary<integer,integer>; foreach var e in a3 do d3[e]:=d3.Get(e)+1; t1:=MillisecondsDelta; Writeln('Заполнены частотные словари: ',t1,' мс'); MillisecondsDelta;
var kd1:=d1.Select(e->e.Key).ToArray; var kd2:=d2.Select(e->e.Key).ToArray; var kd3:=d3.Select(e->e.Key).ToArray; var ki:=kd1.Intersect(kd2).Intersect(kd3); // пересечение ключей t1:=MillisecondsDelta; Writeln('Получено пересечение ключей: ',t1,' мс'); MillisecondsDelta;
foreach var k in kd1 do if not (k in ki) then d1.Remove(k); var v1:=d1.OrderBy(x->x.Key).Select(x->x.Value); foreach var k in kd2 do if not (k in ki) then d2.Remove(k); var v2:=d2.OrderBy(x->x.Key).Select(x->x.Value); foreach var k in kd3 do if not (k in ki) then d3.Remove(k); var v3:=d3.OrderBy(x->x.Key).Select(x->x.Value); var m:=v1.Zip(v2,(x,y)->Min(x,y)).Zip(v3,(x,y)->Min(x,y)).Sum; t1:=MillisecondsDelta; Writeln('Получен результат: ',t1,' мс'); MillisecondsDelta; Writeln(m); end.
Как видно из результатов, в указанных условиях из 6 млн значений отбирается примерно 475 тыс и занимает это порядка полутора секунд на достаточно немолодом ПК c процессором Intel Core 2 Duo (3 ГГц) и 2 Гб оперативной памяти. Вполне приемлемо.
Предлагаю решение на PascalABC.NET. Приводятся тайминги пяти прогонов, разрешение таймера - 16 мс.
Исходные последовательности:
- 1 млн случайных целых из [100;2000];
- 2 млн случайных целых из [50;1500];
- 3 млн случайных целых из [1;1000];
Алгоритм:
- генерируем последовательности;
- создаем и заполняем для каждой последовательности частотный словарь в виде кортежа <ключ><количество>, где ключ - значение элемента, количество - количество раз, которое этот элемент встретился в последовательности;
- создаем последовательности ключей для всех трех словарей и находим их пересечение;
- удаляем из каждого словаря элементы, ключей которых нет в пересечении;
- создаем на основе каждого словаря последовательность значений (частот) и сортируем её по возрастанию;
- для каждой пары значений первой и второй последовательности выбираем минимальное значение, а затем поступаем так же с результирующей и третьей последовательностью, находя в конце сумму её членов.
// PascalABC.NET 3.2, сборка 1374 от 10.01.2017
// Внимание! Если программа не работает, обновите версию!
begin
var t0:=Milliseconds;
var a1:=ArrRandom(1000000,100,2000);
var a2:=ArrRandom(2000000,50,1500);
var a3:=ArrRandom(3000000,1,1000);
var t1:=MillisecondsDelta;
Writeln('Инициализация: ',t1,' мс');
MillisecondsDelta;
var d1:=new Dictionary<integer,integer>;
foreach var e in a1 do d1[e]:=d1.Get(e)+1;
var d2:=new Dictionary<integer,integer>;
foreach var e in a2 do d2[e]:=d2.Get(e)+1;
var d3:=new Dictionary<integer,integer>;
foreach var e in a3 do d3[e]:=d3.Get(e)+1;
t1:=MillisecondsDelta;
Writeln('Заполнены частотные словари: ',t1,' мс');
MillisecondsDelta;
var kd1:=d1.Select(e->e.Key).ToArray;
var kd2:=d2.Select(e->e.Key).ToArray;
var kd3:=d3.Select(e->e.Key).ToArray;
var ki:=kd1.Intersect(kd2).Intersect(kd3); // пересечение ключей
t1:=MillisecondsDelta;
Writeln('Получено пересечение ключей: ',t1,' мс');
MillisecondsDelta;
foreach var k in kd1 do
if not (k in ki) then d1.Remove(k);
var v1:=d1.OrderBy(x->x.Key).Select(x->x.Value);
foreach var k in kd2 do
if not (k in ki) then d2.Remove(k);
var v2:=d2.OrderBy(x->x.Key).Select(x->x.Value);
foreach var k in kd3 do
if not (k in ki) then d3.Remove(k);
var v3:=d3.OrderBy(x->x.Key).Select(x->x.Value);
var m:=v1.Zip(v2,(x,y)->Min(x,y)).Zip(v3,(x,y)->Min(x,y)).Sum;
t1:=MillisecondsDelta;
Writeln('Получен результат: ',t1,' мс');
MillisecondsDelta;
Writeln(m);
end.
Результаты
Инициализация: 234 мс
Заполнены частотные словари: 312 мс
Получено пересечение ключей: 0 мс
Получен результат: 1000 мс
474970
Инициализация: 234 мс
Заполнены частотные словари: 312 мс
Получено пересечение ключей: 16 мс
Получен результат: 984 мс
474137
Инициализация: 250 мс
Заполнены частотные словари: 312 мс
Получено пересечение ключей: 16 мс
Получен результат: 984 мс
474176
Инициализация: 234 мс
Заполнены частотные словари: 312 мс
Получено пересечение ключей: 0 мс
Получен результат: 1000 мс
474090
Инициализация: 234 мс
Заполнены частотные словари: 312 мс
Получено пересечение ключей: 16 мс
Получен результат: 984 мс
474108
Как видно из результатов, в указанных условиях из 6 млн значений отбирается примерно 475 тыс и занимает это порядка полутора секунд на достаточно немолодом ПК c процессором Intel Core 2 Duo (3 ГГц) и 2 Гб оперативной памяти. Вполне приемлемо.