Алгоритм сортировки по сложному условию.

[phprus]

Алгоритм сортировки по сложному условию.

Имеется массив струкрур:
typedef struct {
long long did;
long long sid;
double w;
} E;
E vector[100000];//длинна взята совершенно произвольно, но это не важно.

Массив может быть довольно длинный. В среднем его длинна находится в районе 20 - 30 тысяч злементов. Нужно отсортировать этот массив по полю w (в порядке убывания) при этом сгруппировав записи по полю sid (сортировать эти группы надо по максимальному значению поля w в этой группе) и кроме этого необходимо подсчитать сколько всего различных sid встречается в этом массиве. При этом все это необходимо сделать как можно быстрее.

Вот пример значений:
До:

did	sid	w
1	1	0,4
3	2	0,5
2	1	1

После:

did	sid	w
2	1	1
1	1	0,4
3	2	0,5
разных sid = 2

Вот уже несколько деней думаю и не знаю как это можно сделать. Помогите пожалуйста с алгоритмом. Код можно не приводить ибо реализовываться все это будет скорее всего на C или C++

 

[varan]

не вижу в примере группировки по sid

 

[StUV]

phprus
хм...
отсортировать массив по sid а затем каждый подмассив по w можешь ?

-~{}~ 22.08.06 18:27:

+
реализация сортировки в с++ stl достаточно хорошо оптимизирована
ты пробовал тестить используя стандартные алгоритмы?
если да - что не устраивает?

зы
если тебе заранее известны диапазоны вариантности значений sid или w можно скомбинировать стандартные средства сортировки с сортировкой за линейное время

 

[phprus]

StUV
Тестить пока не пробовал по тому что не знаю что.

Отсортировать массив сначало по sid, а затем каждую группу по значению параметра w можно. Но вот как потом сортировать группы (те уже отсортированные блоки с одинаковым значением sid)? Они веть разного размера, а добовлять еще один массив указателей на начало каждой группы мне бы не хотелось. Так как это практически удвоение требования к памяти.

-~{}~ 22.08.06 20:45:

А можно узнать почему эту тему перенесли в форум "Вопросы по программированию на РНР"? Она же вроде подходит под описание раздела "Вопросы по теории программирования" - "Специально для обсуждения теоретических задач, методик, алгоритмов, парадигм и др."

 

[rotoZOOM]

Как пример:

struct _E{
long long did;
long long sid;
double w;
   bool operator<(const struct _E& a) const{
         if (a.sid!=sid)return sid<a.sid;
         return w>sid.w+1e-9;
   }
} E;
E mas[100000];

sort (mas,mas+n);
// после этого массив будет отсортирован как надо
// сложность сортировки O(n*log2(n))

Думаю, что это самый быстрый универсальный способ.
В скорости можно выиграть, если знать ограничение на входные данные (как говорил StUV).
Для массива в районе 20-30 тыс. элементов на компьютере
Celeron 1200 отсортируется примерно за 50 мс.

 

[phprus]

rotoZOOM
Спасибо проверю на небольшом тестовом наборе. А можно узнать зачем надо прибавлять 1e-9?

P.S. А все таки можно узнать почему эту тему перенесли в форум "Вопросы по программированию на РНР"? Она же вроде подходит под описание раздела "Вопросы по теории программирования" - "Специально для обсуждения теоретических задач, методик, алгоритмов, парадигм и др."

 

[rotoZOOM]

phprus Прибавлять 1e-9 (или eps) необходимо для точности сравнения. Как известно дробные числа в компе представлены с невысокой точностью и может иметь место погрешность сравнение. Добавляя некий Эпсилон мы можем быть уверены, что A точно больше B.

 

[SiMM]

> Прибавлять 1e-9 (или eps) необходимо для точности сравнения.
Да вот нихрена подобного.

 

[rotoZOOM]

SiMM Смелое утверждение. Сколько раз сам натыкался на такое. Какие возражения ?

-~{}~ 22.08.06 23:48:

Примера ради:
считаем такое выражение:

1/2 * (2/3) * (3/4) * ... * (n-1)/n == 1/n

double    a,b;
int           i;
	a=1.0/100000.0;
	b=1.0;
	for (i=1;i<100000;i++)b=b*(i*1.0/(i+1.0));

	if (a>b){
		printf ("Hello, SiMM !\n");
	}

Не поверите, напечатает "Hello, SiMM!"
Вам ли объяснять про неточность хранения чисел с плавающей запятой ?

 

[SiMM]

> Какие возражения ?
Слышали звон, да не знаете, где он. Вам бы непомешало проштудировать арифметико-логические основы ЭВМ (то, что касается представления чисел с плавающей запятой) + вычислительную математику. А в кратце:
1. Числа в компьютере хранятся с фиксированной точностью.
2. Два числа с фиксированной точностью сравниваются друг с другом абсолютно точно, путём вычитания одного из другого. Все остальные заморочки с выравниванием порядка и коррекцией мантиссы - в вышеназванных основах. Хотя для сравнения с нулём многое из этого не нужно - достаточно сравнить знаки чисел, если они одинаковы - порядки чисел, и, наконец, если они равны, мантиссы.

PS: eps имело бы смысл, если бы Вы, к примеру, искали корни уравнения. В этом случае действительно никто не стремится получить абсолютный ноль (это может быть просто невозможно в силу специфики представления чисел) - достигают лишь результата, когда модуль значения функции в точке не превышает зараннее заданной погрешности eps.

-~{}~ 22.08.06 21:53:

rotoZOOM, какое отношение вышеприведённый пример имеет к сравнению двух чисел?

 

[rotoZOOM]

SiMM Хорошо, я согласен, выразился неверно. Естественно компьютер сравнивает два числа с плавающей запятой (в фиксированном представлении) абсолютно точно, но мы не знаем чему РЕАЛЬНО равны эти числа. По каким формулам они считались. Автор ничего не сказал об этом.
Если он вручную вбивает каждое такое число, то да, сравнивать можно без eps. Но если это w получается в результате сложных арифметических вычислений, то я бы побоялся так открыто ставить ">" либо "<".

 

[SiMM]

До кучи, чтобы быстрее доходило
a.sid = sid
w = 1e-10
sid.w = 0

> но мы не знаем чему РЕАЛЬНО равны эти числа. По каким формулам они считались. Автор ничего не сказал об этом.
Без разницы. Это уже автора проблемы, а не сортировки.

 

[phprus]

rotoZOOM
Спасибо за алгоритм сравнения. вроде все работает как надо.

Если он вручную вбивает каждое такое число,

Вручную вводить 10000 чисел? нет они считаются по некой формуле.

 

[rotoZOOM]

SiMM Опять же 1e-9 - это всего лишь пример. Пусть автор сам выставляет такую точность какая ему нужна.
Естественно, для вышеуказанного примера с eps=1e-9 числа будут признаны равными.

 

[SiMM]

> для вышеуказанного примера с eps=1e-9 числа будут признаны равными.
Ничего подобного, всё гораздо запущеннее

> Пусть автор сам выставляет такую точность какая ему нужна.
Автор вообще ничего выставлять не должен. Разве что ноль. Алгоритм сортировки - это алгоритм сортировки, а не гадалка, откуда пришли данные.

 

[phprus]

Я и так ничего выставлять не собираюсь. Разве что 0. Ибо я не понимаю какой смысл в таком прибавлении кроме как дополнительные тормоза при складывании вещественных чисел.

Данные пришли из функции. А она их вычислила на базе имеющихся в ее распоряжении данных. Но это уже другая история.

 

[rotoZOOM]

Ничего подобного, всё гораздо запущеннее

Вы меня заинтриговали. Куда запущеннее ?

Автор вообще ничего выставлять не должен. Разве что ноль. Алгоритм сортировки - это алгоритм сортировки, а не гадалка, откуда пришли данные.

Вот ! Именно этот ноль (бесконечно малое eps) он и выставляет Ну это понятно, что алгоритму сортировки по барабану и откуда пришли данные, и что это вообще за объекты, которые он сортирует, но вот функции сравнения, которую вызывает этот алгоритм, не совсем параллельно.

 

[SiMM]

> Вы меня заинтриговали. Куда запущеннее ?
Возьмите да подставьте числа.

> но вот функции сравнения, которую вызывает этот алгоритм, не совсем параллельно
Абсолютно параллельно. Она понятия не имеет, откуда они, да ей это и не нужно.

 

[rotoZOOM]

SiMM Это уже беспредметный спор. Вот не поленился и подставил. Вышло именно так, как и ожидалось. Числа признаются равными и их место в результирующем массиве четко не определено. А что я должен был увидеть ?

> но вот функции сравнения, которую вызывает этот алгоритм, не совсем параллельно
Абсолютно параллельно. Она понятия не имеет, откуда они, да ей это и не нужно.

Она может и да, но автору - нет. (сейчас можно уйти в рекурсию и не вернутся . Предполагаю дальнейший ответ:"Автору тоже параллельно", так ?

 

[phprus]

Да паралельно. Ибо иначе я бы использовал алгоритм устайчивой сотировки stable_sort вместо простого sort