nth_element [Решено]

[Igors]

Добрый день

Есть std ф-ция nth_element, напомню что она делает: упорядочивает массив/контейнер так чтобы все элементы меньше заданного значения стояли слева, в все больше - справа. Размеры левой и правой частей будут "как получится", внутри частей элементы не упорядочены.

Нужно: почти то же самое но так чтобы части были равны, пример
{ 9, 5, 7, 1, 3 }  // исходный
{ 3, 1, 5, 9, 7 }  // 5 точно посередине, слева все <= 5 справа все >= 5

Результат легко достигается сортировкой, но это заметно тормозит. "Ф-ции не нашел" в написать сам затрудняюсь. Что предложите?

Спасибо

 

[V1KT0P]

Если я тебя понял, то тебе нужна функция которая делит массив пополам, и центральное число массива делит на массив так, что слева меньше, а справа больше?
Тогда сперва надо найти это число, переместить в центр, а затем на одном проходе массива переместить меньшие значения влево, а большие в право. Если можно создавать новый массив, то алгоритм получится банальный, если нельзя то получится мудреная тасовка. А вот как найти центральное число что-то в голову не приходит щас.

[Igors]

Если я тебя понял, то тебе нужна функция которая делит массив пополам, и центральное число массива делит на массив так, что слева меньше, а справа больше?

Да, именно так

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

Ясно что если бы "5" было заранее известно - просто вызвал бы nth_element, или сам бы написал без проблем, там ничего мудреного. Так его ж нет

[V1KT0P]

Ясно что если бы "5" было заранее известно - просто вызвал бы nth_element, или сам бы написал без проблем, там ничего мудреного. Так его ж нет

Нагуглил как называется эта задача "Нахождение к-того минимального элемента". Можешь нагуглить нужное по запросу "Selecting k smallest", либо взять готовое из библиотеки GSL: http://www.gnu.org/software/gsl/
Одна из этих функций подойдет для тебя: http://www.gnu.org/software/gsl/manual/html_node/Selecting-the-k-smallest-or-largest-elements.html

[Igors]

нужное по запросу "Selecting k smallest", либо взять готовое из библиотеки GSL: http://www.gnu.org/software/gsl/
Одна из этих функций подойдет для тебя: http://www.gnu.org/software/gsl/manual/html_node/Selecting-the-k-smallest-or-largest-elements.html

Не то

12.3 Selecting the k smallest or largest elements

The functions described in this section select the k smallest or largest elements of a data set of size N. The routines use an O(kN) direct insertion algorithm which is suited to subsets that are small compared with the total size of the dataset. For example, the routines are useful for selecting the 10 largest values from one million data points, but not for selecting the largest 100,000 values.

Это прямая вставка в выходной массив который поддерживается сортированным

Но все равно - спасибо за хлопоты

[V1KT0P]

Это прямая вставка в выходной массив который поддерживается сортированным

Вот еще один алгоритм: http://pine.cs.yale.edu/pinewiki/QuickSelect. Именно то что нужно, но он требует для своей работы два рабочих массива. Хотя если у тебя массивы не слишком большие и ты можешь держать в памяти два рабочих массива постоянно то думаю этот алгоритм подойдет.
Ну и статья в википедии: http://en.wikipedia.org/wiki/Selection_algorithm
Вот тут еще можешь поискать: http://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on

[Anchorite]

По моему имеет смысл поглядеть в исходники qsort.
Единственное что не нужно делать - рекурсивно сортировать подмассивы.

[Igors]

По моему имеет смысл поглядеть в исходники qsort.
Единственное что не нужно делать - рекурсивно сортировать подмассивы.

Наверное qSort или QuickSort (но не qsort из stdlib). Там ничего нового - просто nth_element, размеры подмассивов как получится

[Anchorite]

Тогда не совсем понятна постановка задачи.

Что значит:

Нужно: почти то же самое но так чтобы части были равны, пример

Что должно получится на выходе, когда на вход попадает массив с четной длинной?

И почему не подходит

Код:

nth_element (myvector.begin(), myvector.begin() + myvector.size() / 2, myvector.end());

[V1KT0P]

Наверное qSort или QuickSort (но не qsort из stdlib). Там ничего нового - просто nth_element, размеры подмассивов как получится

Подходит ли для тебя изменение массива переданного в функцию?
Меня задача заинтересовала, но решать не хочется пока не появятся критерии решения. А именно тестового проекта с текущим решением с замерами скорости работы и задачи во сколько надо ускорить работу.

[Igors]

Тогда не совсем понятна постановка задачи.

Что значит:

Нужно: почти то же самое но так чтобы части были равны, пример

Что должно получится на выходе, когда на вход попадает массив с четной длинной?

И почему не подходит

Код:

nth_element (myvector.begin(), myvector.begin() + myvector.size() / 2, myvector.end());

Неоднократно замечал как сразу постановка становится "плохой" если задача не решается сразу, т.е. дело не сводится к простой эксплуатации знаний Ведь неск раз уже было сказано - nth делит на подмассивы размеры которых "как получится", а мне нужно "заданного". Так чего упираться и месить по-пустому?  

Подходит ли для тебя изменение массива переданного в функцию?

Не только подходит, но и является целью

Вот еще один алгоритм: http://pine.cs.yale.edu/pinewiki/QuickSelect. Именно то что нужно, но он требует для своей работы два рабочих массива. Хотя если у тебя массивы не слишком большие и ты можешь держать в памяти два рабочих массива постоянно то думаю этот алгоритм подойдет.
Ну и статья в википедии: http://en.wikipedia.org/wiki/Selection_algorithm
Вот тут еще можешь поискать: http://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on

Ну с временными массивами явное фуфло. Их там нужно не один а рекурсивно, и потом хз как их склеивать. А так у меня и сделано как пишут (передрал из книги Дженсена).

Код

C++ (Qt)
void median_split(
	double * data,		// data array				
	int start,         	// start index in array
	int end,           	// end index in array
	int median ) 	// desired median index
{
	int left = start;
	int right = end;
 
	while (right > left) {
		double v = data[right];
		int i = left - 1;
		int j = right;
		for (;;) {
			while (data[++i] < v)
			;
			while (data[--j] > v && j > left)
			;
			if (i >= j) break;
			std::swap(data[i], data[j]);
		}
 
		std::swap(data[i], data[right]);
		if (i >= median)
			right = i - 1;
		if (i <= median)
			left = i + 1;
	}
}
 

И все бы ничего, но в какие-то моменты наступает жуткий тормоз, вот надо разобраться почему

Общая задача - построение дерева без доп данных (ну почти), ноды находятся по индексу

[Anchorite]

Неоднократно замечал как сразу постановка становится "плохой" если задача не решается сразу, т.е. дело не сводится к простой эксплуатации знаний Ведь неск раз уже было сказано - nth делит на подмассивы размеры которых "как получится", а мне нужно "заданного". Так чего упираться и месить по-пустому?  

Ну да, конечно. Все должны уметь читать твои мысли.

По поводу

...nth делит на подмассивы размеры которых "как получится"...

может стоит обратить внимание на второй аргумент этой функции?

И кстати, твой median_split(double * data,      // data array            
   int start,            // start index in array
   int end,              // end index in array
   int median
)

отлично переписывается при помощи nth_element вот таким образом

Код:

median_split(double* data,		// data array				
	int start,         	// start index in array
	int end,           	// end index in array
	int median
)
{
    nth_element(data + start, data + median, data + end + 1);
}

[V1KT0P]

И все бы ничего, но в какие-то моменты наступает жуткий тормоз, вот надо разобраться почему

Скинь массив на котором тормоза происходят.

[Igors]

Скинь массив на котором тормоза происходят.

Не транспортабельный (порядка 2 Gb). Изучал в отладчике, вроде получается что тормоз настает когда массив сортирован (ну или почти)

может стоит обратить внимание на второй аргумент этой функции?

Да! nth_element и делит как мне надо, "по индексу" (а не "по значению"), и это действие не равно тому что делает qSort. Перемудрил 

Спасибо Anchorite, V1KT0P