Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Кризис в самообразовании.
Форум разработчиков электроники ELECTRONIX.ru > Сайт и форум > Образование в области электроники
Страницы: 1, 2, 3, 4, 5
blackfin
Mar 28 2017, 03:12
На чистом "С" задача решается в три шага:
Код
#define swap(x,y) s = x; x = y; y = s;

#define N 19

int main()
{
    int s;
    int i = 0;
    int j = N-1;

// Шаг №1:
    do {
        while ((rnd[i]%2 == 0)&&(i != j)) i = i + 1;
        while ((rnd[j]%2 == 1)&&(j != i)) j = j - 1;
        swap(rnd[i],rnd[j]);
    } while (i != j);

// Шаг №2:
    if (1 < i)
    {
        if (rnd[N-1]%2 == 0)  i = i + 1;

        сортировка_первых_i_значений_rnd[]_по_убыванию
    }

// Шаг №3:
    if (j < N-1)
    {
        сортировка_последних_N-j_значений_rnd[]_по_возрастанию
    }

    return 0;
}
Эдди
Mar 28 2017, 04:58
Цитата(TSerg @ Mar 28 2017, 01:07) *
наезды на технологии

Я на технологии не наезжаю, я лишь критикую всякую дрянь: мастдайку, systemd'изированные дистры линукса, наркоманские ЯП и т.п.
ViKo
Mar 28 2017, 10:26
Я очень слабый умелец в C#. Вот, сделал. Можно поводить мордой по батарее, если что не так.
CODE

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace VS_2017_ArraySort {

public class myComparer : IComparer {

public int Compare(object x, object y ) {
if (x == y) return 0;
else if (((int)x % 2) == 1 && ((int)y % 2) == 0) return 1;
else if (((int)x % 2) == 0 && ((int)y % 2) == 0 && ((int)x < (int)y)) return 1;
else if (((int)x % 2) == 1 && ((int)y % 2) == 1 && ((int)x > (int)y)) return 1;
else return -1;
}
}

class Program {
static void Main(string[] args) {
IComparer myComp = new myComparer();

const int N = 20;
int[] Arr = new int[N];
Random Rnd = new Random();

for (int i=0; i<N; i++) {
Arr[i] = Rnd.Next(0, 99);
}
Console.Write("Исходный массив: ");
foreach (int i in Arr)
Console.Write(i + " ");
Console.WriteLine();

Array.Sort(Arr, myComp);
Console.Write("После сортировки: ");
foreach (int i in Arr)
Console.Write(i + " ");
Console.WriteLine();
}
}
}

Исходный массив: 71 58 3 51 65 96 9 16 57 85 32 75 3 98 51 53 69 15 39 1
После сортировки: 98 96 58 32 16 1 3 3 9 15 39 51 51 53 57 65 69 71 75 85
Swup
Mar 28 2017, 11:17
Цитата(ViKo @ Mar 28 2017, 14:26) *
Я очень слабый умелец в C#. Вот, сделал. Можно поводить мордой по батарее, если что не так.
Код
Array.Sort(Arr, myComp);


Там ведь используется интроспектная сортировка. Такая комбинация перестановок, сортировок вставкой, кучей и быстрой.
При определенном размере массива будет работать быстрая сортировка, а она делается не на месте. Т.е. в общем случае нарушается условие задачи.

ПС понравилась функция сравнения у вас. Мне и в голову не пришло, что так можно.
ViKo
Mar 28 2017, 11:26
Цитата(Swup @ Mar 28 2017, 14:17) *
При определенном размере массива будет работать быстрая сортировка, а она делается не на месте. Т.е. в общем случае нарушается условие задачи.

Почему не на месте? В книге Шилдта есть такой код:
Код
/* Quicksort setup function. */
void quick(char *items, int count)
{
  qs(items, 0, count-1);
}  
/* The Quicksort. */
void qs(char *items, int left, int right)
{
  register int i, j;
  char x, y;
  i = left; j = right;
  x = items[(left+right)/2];
  do {
    while((items[i] < x) && (i < right)) i++;
    while((x < items[j]) && (j > left)) j--;
    if(i <= j) {
      y = items[i];
      items[i] = items[j];
      items[j] = y;
      i++; j--;
    }
  } while(i <= j);
  if(left < j) qs(items, left, j);
  if(i < right) qs(items, i, right);
}
dxp
Mar 28 2017, 11:28
Сортировка in-place:

CODE
#!/usr/bin/python3

rnd =  [40,14,17,46,12,53,3,49,26,56,10,28,59,20,35,42,42,18,24]

rnd.sort(key=lambda x: -1*x if x & 0x1 else x, reverse=True)

print (rnd)


CODE
hz@h:~/slon/python/$ ./sort2.py
[56, 46, 42, 42, 40, 28, 26, 24, 20, 18, 14, 12, 10, 3, 17, 35, 49, 53, 59]

Этот вариант и работать должен быстрее. Хотя он не такой наглядный для неподготовленного человека.
=SSN=
Mar 28 2017, 11:31
Цитата(Swup @ Mar 28 2017, 14:17) *
ПС понравилась функция сравнения у вас. Мне и в голову не пришло, что так можно.

Указатель на функцию-предикат можно также и на С++ использовать:
Код
// Return whether first element is greater than the second
bool greater ( int a, int b )
{
   return (a&1 == 0)&&(b&1 == 0)&&(a < b)||(a&1 == 1)&&(b&1 == 1)&&(a > b)||(a&1 == 1)&&(b&1 == 0);
}

sort( vec.begin( ), vec.end(), greater);

См. msdn
TSerg
Mar 28 2017, 11:54
Цитата(dxp @ Mar 28 2017, 14:28) *
rnd.sort(key=lambda x: -1*x if x & 0x1 else x, reverse=True)
..
Хотя он не такой наглядный для неподготовленного человека.

Да, с лямбда-функцией это практически идеальный по краткости вариант.
Нечто подобное было предложено на PascalABC.Net (там тоже lambda есть), но студент выбрал из предложенных все же вариант с декомпозицей на четные-нечетные и раздельной их сортировкой пузырьком на месте.
Так ему понятнее.

Код
// Body  
  var k: integer = 0;
  var x: integer;
  
// Even to head
  for var i := 0 to ar.High do
    if not Odd(ar[i]) then begin
        x := ar[i];
        for var j := i downto k+1 do
          ar[j] := ar[j-1];
        ar[k] := x;
        Inc(k);
    end;
// Sort even
  for var i := 0 to k-2 do
    for var j := i to k-1 do
      if ar[i] < ar[j] then Swap(ar,i,j);
// Sort odd
  for var i := k to ar.High-1 do
    for var j := i to ar.High do
      if ar[i] > ar[j] then Swap(ar,i,j);


dxp
Mar 28 2017, 12:18
Замерил производительность, сортировка 1000000 рандомов в диапазоне 0..100000. Первый вариант (с вычленением чётных-нечётных и раздельной сортировкой):

1.0882549455855042

второй, по ключу:

0.48738399290014056

Более, чем в два раза.

P.S. Вариант с лямбдой работает только с натуральными числами. Если надо весь целый диапазон, то ключевую функцию надо поправить соответственно.
Swup
Mar 28 2017, 12:27
Цитата(ViKo @ Mar 28 2017, 15:26) *
Почему не на месте? В книге Шилдта есть такой код:


Спасибо, что поправили.
Какие-то у меня в голове странные ассоциации сложились по поводу "на месте" и "O(1) потребления памяти".
aiwa
Mar 28 2017, 13:16
Цитата(dxp @ Mar 27 2017, 10:43) *
А уж про синтаксические правила и говорить нечего. Ведь это же надо придумать конструкции вроде такой:

int (*(af[]))(int);

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


Можно разобраться и без бутылки, если помнить, что в С разбор не слева-направо или наоборот, а по спирали.

Берем идентификатор и вокруг него раскручиваем спиральку:
af /*af - идентификатор*/
[] /*значит, af - это массив*/
* /*значит, это массив указателей на...*/
(int) /* скобки - принадлежность функции, внутри скобок - ее параметры, значит массив указателей на функции принимающие в качестве параметра тип int */
int /* тип возращаемого результата вышеупомянутыми функциями, ...... */
AlexandrY
Mar 28 2017, 19:44
Цитата(dxp @ Mar 27 2017, 18:24) *
Было сказано, чтобы читабельно и понимабельно бегиннерам - т.е. разумная декомпозиция. Но для любителей говнокода, извольте:
Код
res  = sorted([x for x in rnd if not x%2], reverse=True) + sorted([x for x in rnd if x%2])

Нет, ну действительно у создателей питона не было целью сделать жизнь легче.

Вот пример на Node.js -
Код
var math = require('mathjs');

var  X = math.matrix([40, 14, 17, 46, 12, 53, 3, 49, 26, 56, 10, 28, 59, 20, 35, 42, 42, 18, 24]);
A = math.concat(math.sort(math.filter(X, function (x){ return x%2 == 0 }),'desc'),math.sort(math.filter(X, function(x){ return x%2 > 0})))

console.log(A);
Все ясно и понятно. Я это сделал за 10 мин, до этого никогда Node.js в руках не держал.

А вооще-то мы ждем перлов на ассемблере. Кто тут рвался показать счастье. biggrin.gif

Да нет, я не тролю. Тема мне не интересна, просто только что мне пришла ссылка с рекламой Node.js для embedded,
где довольно изящно опустили Python - http://embedded-computing.com/articles/spe...-using-node-js/
TSerg
Mar 28 2017, 21:01
Цитата(AlexandrY @ Mar 28 2017, 22:44) *
.. до этого никогда Node.js в руках не держал.

Кто хорошо освоил один из ЯП, нет проблем перейти на другой.
Точнее, проблемы будут, но не с синтаксисом, а либами.
P.S.
Питон - это не панацея, но один из вариантов современных языковых технологий.


Нда.. наверное самый короткий и понятливый вариант на PascalABC.Net (используются лямбды):
Есть конечно, фикус - массив остается прежним sm.gif

Код
begin
  var ar := Seq(45,46,8,11,5,29,37,0,21,43,4,5,58,34,14,18,40,46,30);
  ar.Where(x -> x mod 2 = 0).SortedDescending.Print;
  Print('');
  ar.Where(x -> x mod 2 <> 0).Sorted.Print;
end.


Result:
Код
45 46 8 11 5 29 37 0 21 43 4 5 58 34 14 18 40 46 30
58 46 46 40 34 30 18 14 8 4 0 5 5 11 21 29 37 43 45
dxp
Mar 29 2017, 04:00
QUOTE (AlexandrY @ Mar 29 2017, 02:44) *
Нет, ну действительно у создателей питона не было целью сделать жизнь легче.

Конечно! Питон - один из самых внятных и простых в освоении языков и при этом невероятно мощный и гибкий. Но вы-то его не знаете ни разу, а поливать дерьмом то, что с чем не удосужились познакомиться даже поверхностно, это ваша фирменная фишка. Это касается и С++, и систем управления версиями, а вот теперь ещё и питон.

QUOTE (AlexandrY @ Mar 29 2017, 02:44) *
Вот пример на Node.js -
CODE
var math = require('mathjs');

var  X = math.matrix([40, 14, 17, 46, 12, 53, 3, 49, 26, 56, 10, 28, 59, 20, 35, 42, 42, 18, 24]);
A = math.concat(math.sort(math.filter(X, function (x){ return x%2 == 0 }),'desc'),math.sort(math.filter(X, function(x){ return x%2 > 0})))

console.log(A);
Все ясно и понятно. Я это сделал за 10 мин, до этого никогда Node.js в руках не держал.

Что тут ясно и понятно? Какое-то нагромождение "проприетарных" ключевых слов. При этом длинно и рыхло. Уже приводил выше, но повторю:
CODE
rnd.sort(key=lambda x: -1*x if x & 0x1 else x, reverse=True)

Сделайте хотя бы так же компактно. Хотя, думается, вы не понимаете, как это работает.

QUOTE (AlexandrY @ Mar 29 2017, 02:44) *
А вооще-то мы ждем перлов на ассемблере. Кто тут рвался показать счастье. biggrin.gif

Про асм тоже не в кассу. Во-первых, все поняли контекст того поста (ну, кроме вас, видимо). Во-вторых, вся фишка этих кратких и красивых вариантах на ЯВУ - в использовании библиотек. Напишите сортировку на любом из этих языков без использования библиотечных функций - чисто выражениями языка - и увидите, что на асме оно будет не сильно отличаться, потому что тут нет ни каких-либо высокоуровневых абстракций, ни сколько-нибудь сложной структуры программы.
TSerg
Mar 29 2017, 15:58
Цитата(dxp @ Mar 29 2017, 07:00) *
.. вся фишка этих кратких и красивых вариантах на ЯВУ - в использовании библиотек.

Не только.
Есть такие понятия, как "синтаксический сахар" и "синтаксическая соль".
Применение первого, обеспечивает, по выражению Джек Криншоу:
"В конце концов, люди тоже должны читать программы… Сахарные токены служат в качестве полезных ориентиров, помогающих вам не сбиться с пути…"
Сам термин "syntactic sugar" был введен Peter J. Landin в 1964 г. для описания синтаксиса алголо-подобного языка с использованием лямбда-исчисления.
Пример во многих ЯВУ - дополнение базового безусловного цикла, сначала тремя циклами (пред-, пост-условие, цикл с шагом), а затем и foreach.
Или, к примеру (x := x + y) == (x+=y); Это стандартно для C, но для Pascal - нет. Тем не менее, отечественные разработчики PascalABC.Net, сознательно пошли на значительную переделку Object Pascal, для сближения его с современными технологиями.

Синтаксическая "соль" - дополнительные, технически бесполезные, конструкции в языке программирования, которые правила языка требуют употреблять при выполнении потенциально небезопасных действий.
Пример в Delphi - override.
Или, например - завершение операции точкой с запятой.
Для синтаксического парсера, это не принципиально, но большинство разработчиков к этому привыкли.
MrYuran
Mar 30 2017, 10:12
Цитата(TSerg @ Mar 29 2017, 18:58) *
Или, к примеру (x := x + y) == (x+=y); Это стандартно для C, но для Pascal - нет.

Это имеет конечный смысл, особенно на безаккумуляторных архитектурах.
Так же, как ++ и --
petrov
Mar 30 2017, 14:20
Цитата(TSerg @ Mar 29 2017, 18:58) *
Или, к примеру (x := x + y) == (x+=y); Это стандартно для C, но для Pascal - нет. Тем не менее, отечественные разработчики PascalABC.Net, сознательно пошли на значительную переделку Object Pascal, для сближения его с современными технологиями.


Просто таки замечательный пример тарабарщины на ровном месте, в большинстве современные языки превратились в совершенно нечитабельную вещь в себе, в отличие от старых книг с алгоритмами на фортране и паскале. ИМХО
TSerg
Mar 31 2017, 18:29
Цитата(petrov @ Mar 30 2017, 17:20) *
Просто таки замечательный пример тарабарщины на ровном месте, в большинстве современные языки превратились в совершенно нечитабельную вещь в себе, в отличие от старых книг с алгоритмами на фортране и паскале. ИМХО

BASIC - наше все, с нумерацией строк, GOSUB и полной свободой.
TSerg
Apr 4 2017, 17:12
Еще один, очень красивый и, практически, кросс-языковый вариант решения задачи сортировки четных-нечетных:
(хотя он подразумевает, что изначально числа заданы в положительном диапазоне)

Код
for (int i = 0; i < rnd.Length; i++) if (rnd[i] % 2 == 0) rnd[i] = rnd[i] * (-1);
Array.Sort(rnd);
for (int i = 0; i < rnd.Length; i++) if (rnd[i] % 2 == 0) rnd[i] = rnd[i] * (-1);
dxp
Apr 5 2017, 03:20
QUOTE (TSerg @ Apr 5 2017, 00:12) *
Еще один, очень красивый и, практически, кросс-языковый вариант решения задачи сортировки четных-нечетных:
(хотя он подразумевает, что изначально числа заданы в положительном диапазоне)

CODE
for (int i = 0; i < rnd.Length; i++) if (rnd[i] % 2 == 0) rnd[i] = rnd[i] * (-1);
Array.Sort(rnd);
for (int i = 0; i < rnd.Length; i++) if (rnd[i] % 2 == 0) rnd[i] = rnd[i] * (-1);

Ну, так в варианте в посте №106 именно этот финт и использован. И тоже только для положительных целых. Для любых целых это трансформируется в
CODE
rnd.sort(key=lambda x: (1, -1*x) if x & 0x1 else (0, x), reverse=True)
TSerg
Apr 5 2017, 13:53
Цитата(dxp @ Apr 5 2017, 06:20) *
Ну, так в варианте в посте №106 именно этот финт и использован. И тоже только для положительных целых.

Разумеется, просто здесь без лямбд.
А так, да - Ваш на первой полочке, хотя и с ограничением на диапазон.

Вот без ограничений на знак:
Код
const
  m=-MaxInt-1;

for i:=0 to Length(Arr)-1 do Arr[i]:=(Arr[i] xor m) shr 1 xor -(Arr[i] and 1 xor 1);
Sort(Arr);
for i:=0 to Length(Arr)-1 do Arr[i]:=(Arr[i] shl 1 xor m) xor -(Arr[i] shr 31) xor 1;
ViKo
Apr 5 2017, 14:08
Два раза бегать по массиву - это чемпион? w00t.gif
TSerg
Apr 5 2017, 14:31
Цитата(ViKo @ Apr 5 2017, 17:08) *
Два раза бегать по массиву - это чемпион? w00t.gif

Где сказано, что это "чемпион"?
Да и два раза пробежаться - это линейная сложность.
ViKo
Apr 5 2017, 14:40
Два раза бегать или сортировать только натуральные числа - такая альтернатива?
Два раза бегать - это два раза. Сегодня в обед испытал удовольствие, забыл кошелек, обнаружил уже у кассы. К черту такую линейную сложность.
TSerg
Apr 5 2017, 14:47
Цитата(ViKo @ Apr 5 2017, 17:40) *
Два раза бегать или сортировать только натуральные числа - такая альтернатива?
Два раза бегать - это два раза. Сегодня в обед испытал удовольствие, забыл кошелек, обнаружил уже у кассы. К черту такую линейную сложность.

Вам хочется поспорить ни о чем? Предоставляю это увлекательное занятие в форме Вашего же само-диалога.
ViKo
Apr 5 2017, 15:57
Здесь не о чем спорить. Констатация факта в форме вопроса.
dxp
Apr 6 2017, 04:17
QUOTE (TSerg @ Apr 5 2017, 20:53) *
Разумеется, просто здесь без лямбд.

Да тут не в лямбдах дело. Лямбда - это просто способ внедрить тело функции в выражение. Предыдущий пример без лямбды:
CODE
def get_key():
    return (1, -1*x) if x & 0x1 else (0, x)

rnd.sort(key=get_key(), reverse=True)


QUOTE (TSerg @ Apr 5 2017, 20:53) *
А так, да - Ваш на первой полочке, хотя и с ограничением на диапазон.

Предыдущий пример (120-й пост и этот выше) без ограничений на диапазон.

QUOTE (ViKo @ Apr 5 2017, 21:08) *
Два раза бегать по массиву - это чемпион? w00t.gif

А сколько проходов по массиву совершается внутри функции сортировки? Или вы полагаете, что внутри sort() оно за один проход сортирует? И вообще, каков вес (в смысле затрат) прохода по массиву - сиречь, работа с памятью, - на фоне операций сортировки?
ViKo
Apr 6 2017, 05:10
Цитата(dxp @ Apr 6 2017, 07:17) *
А сколько проходов по массиву совершается внутри функции сортировки? Или вы полагаете, что внутри sort() оно за один проход сортирует? И вообще, каков вес (в смысле затрат) прохода по массиву - сиречь, работа с памятью, - на фоне операций сортировки?

Логично, что того, кто пробежал дополнительный круг, вряд ли назовут чемпионом. Вот последнее ваше решение вполне может претендовать. Наряду с подобными на других языках - функция метода сравнения + сама библиотечная функция сортировки. Правда, ничего восхитительного в этом нет. Казуальное решение, оно и есть лучшее.
Количество проходов от функции сортировки зависит. Будем считать, используется быстрая. Сколько надо, столько и есть. Проход по массиву с инвертированием членов, удовлетворяющих условию, думаю, соизмерим с проходом со сравнением пары и обменом местами.
dxp
Apr 6 2017, 07:43
QUOTE (ViKo @ Apr 6 2017, 12:10) *
Логично, что того, кто пробежал дополнительный круг, вряд ли назовут чемпионом.

Сперва надо определить, что есть "дополнительный круг". Если предварительная подготовка данных упрощает дальнейшую обработку так, что там в разы всё легче и быстрее, это как раз "сокращение дистанции", а не "дополнительный круг".

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

QUOTE (ViKo @ Apr 6 2017, 12:10) *
Вот последнее ваше решение вполне может претендовать. Наряду с подобными на других языках - функция метода сравнения + сама библиотечная функция сортировки.

Так у TSerg по сути используется тот же метод. В моём примере выполняется подготовка ключей - массив элементов, каждый из которых связан с целевым сортируемым элементом, а затем собственно сортировка целевых элементов на основе значений ключей. У TSerg делается принципиально то же самое: сначала он готовит ключи, модифицируя элементы массива так, чтобы они могли выполнять роль ключей, затем сортировка по этим ключам. Ну, и финально вернуть значения элементов массива в исходному виду. Стандартные способы тут ничем не вырвутся вперёд.

QUOTE (ViKo @ Apr 6 2017, 12:10) *
Проход по массиву с инвертированием членов, удовлетворяющих условию, думаю, соизмерим с проходом со сравнением пары и обменом местами.

Проход со сравнением пары и перестановкой местами - это что, "пузыёк"? "Пузырёк" - один из самых медленных (хотя и один из самых простых и незатратных) способов сортировки. Там совершается почти столько проходов по массиву, сколько в массиве элементов. На этом фоне лишний проход по массиву ничего не портит.
ViKo
Apr 6 2017, 07:49
Нет, не "пузырек". Многие функции сортировки работают с парой элементов одинаково - сравнивают и, если нужно, переставляют местами. В том числе и быстрая сортировка.
dxp
Apr 6 2017, 08:37
QUOTE (ViKo @ Apr 6 2017, 14:49) *
Нет, не "пузырек". Многие функции сортировки работают с парой элементов одинаково - сравнивают и, если нужно, переставляют местами. В том числе и быстрая сортировка.

quicksort (который Хоара), насколько мне известно, сравнивает с опорным элементом, а переставляет пару, в которую опорный не входит. Но это не важно. Там всё равно суммарно получается эн проходов по массиву, где эн зависит логарифмически от количества элементов. Да, гораздо лучше "пузырька", особенно, когда элементов много. Один лишний проход снаружи сортировки погоды не портит.
ViKo
Apr 6 2017, 09:54
Цитата(dxp @ Apr 6 2017, 11:37) *
quicksort (который Хоара), насколько мне известно, сравнивает с опорным элементом, а переставляет пару, в которую опорный не входит. Но это не важно. Там всё равно суммарно получается эн проходов по массиву, где эн зависит логарифмически от количества элементов. Да, гораздо лучше "пузырька", особенно, когда элементов много.

В сообщении 105 алгоритм быстрой сортировки показан. Пусть не так работает с парой, это, действительно не существенно.
Цитата
Один лишний проход снаружи сортировки погоды не портит.

Вообще-то, даже два: один до сортировки, один после. А можно без них, внутри функции сортировки все выполнить. Экономия очевидна.
dxp
Apr 6 2017, 10:52
QUOTE (ViKo @ Apr 6 2017, 16:54) *
Вообще-то, даже два: один до сортировки, один после. А можно без них, внутри функции сортировки все выполнить. Экономия очевидна.

Вообще-то, тут не просто сортировка, а сортировка с дополнительным условием (чёт-нечет), и это тоже надо как-то учитывать. Т.е. это выливается в некие дополнительные действия, и не факт, что они будут менее затратными, нежели один доп. проход по массиву.
@Ark
Apr 6 2017, 11:58
Цитата(dxp @ Apr 6 2017, 13:52) *
Вообще-то, тут не просто сортировка, а сортировка с дополнительным условием (чёт-нечет), и это тоже надо как-то учитывать. Т.е. это выливается в некие дополнительные действия, и не факт, что они будут менее затратными, нежели один доп. проход по массиву.

Это все издержки ЯВУ. sm.gif На любом асме эта проблема ничего не стоит. Просто считаем младший бит числа самым старшим и все.
Можете, чисто для удобства, "крутануть" циклически весь регистр вправо, перед сравнением...
Чет будет в начале, нечет - в конце отсортированного списка. Если нужен обратный порядок - инвертируем бит перед сравнением.
P.S. По-моему, основной вопрос для любого языка - кому должно быть "удобно": программисту или процессору? sm.gif

Gruffly
Apr 6 2017, 21:50
Весело тут у Вас sm.gif
Кто-то считает, что линейный пробег по массиву сравним по быстродействию с любой сортировкой, даже самой быстрой?
Таки я его разочарую.
Берем алгоритм из поста #121.
Делаем точные замеры ( на PC, Win7, Delphi 7, размерность времени в мкс) и что видим?
Ой!
- prepare и post - линейная пробежка по массиву;
- sort - сортировка массива методом QuickSort, можно еще Radix-сортировку применить, но не принципиально что-то изменится.

Нажмите для просмотра прикрепленного файла
Нажмите для просмотра прикрепленного файла
ViKo
Apr 7 2017, 04:16
В таблице не хватает процентного отношения (пре + пост) к сорт. Также время сортировки может зависеть от того, какие данные в массиве. Желательно усреднить множество сортировок.
"Кто-то" сравнивает линейный пробег по массиву с одним из проходов функции сортировки. Вот что соизмеримо. Понятно, сортировка 1000-элементного массива будет выполняться проходов за 10 (по фрагментам массива). Здесь вклад дополнительных внешних проходов будет невелик. А вот 10-элементный массив наглядно демонстрирует неоптимальность такого подхода.
Gruffly
Apr 7 2017, 14:15
1. По приведенной выше таблице - можно прикинуть проценты, если кто-то учился в детстве считать в уме.
2. Как я вижу, из постановки задачи, массив формируется из random-чисел и это есть наиболее общая постановка задачи.
Рассматривать особые частные случаи - интересно, но в оговоренных случаях.
3. При рандом-массиве, размерностью свыше нескольких десятков, тем более сотен - QuickSort отработает предсказуемо.
4. При размерности 4..10 - есс-но могут быть реализованы крайне эффективные варианты решения Задачи, да хоть на тех же if..else.
@Ark
Apr 7 2017, 15:04
Цитата(Gruffly @ Apr 7 2017, 00:50) *
Делаем точные замеры ( на PC, Win7, Delphi 7, размерность времени в мкс)...

Объясните, пожалуйста, как сочетаются понятия WIN7 (явно, не real-time) и "точные замеры времени в мкс"?


Gruffly
Apr 7 2017, 15:23
Цитата(@Ark @ Apr 7 2017, 16:04) *
Объясните, пожалуйста, как сочетаются понятия WIN7 (явно, не real-time) и "точные замеры времени в мкс"?


Учить, до посинения, такие вещи, как:

Код
GetThreadPriority(GetCurrentThread );
GetSystemTimeAdjustment(Ad, Int, Q);
QueryPerformanceCounter( i1 );
QueryPerformanceFrequency( i1 );


// System slice, [100*ns]
// 156001 == 15.6001 ms
function GetAccuracy_: Cardinal;
var  Ad, Int: Cardinal;
     Q: LongBool;
begin
  GetSystemTimeAdjustment(Ad, Int, Q);
  Result:= Int;
end;

// CPU frequency, [MHz]
function GetCPUFreq_: extended;
var
    i1,i2,t:int64;
    pr:dword;
begin
    pr := GetThreadPriority(GetCurrentThread );
    SetThreadPriority(GetCurrentThread,THREAD_PRIORITY_TIME_CRITICAL);
    QueryPerformanceCounter( i1 );
    t := GetCPUTicks_;
    Sleep(SleepTime);
    asm
      dw 310Fh // rdtsc
      sub eax, dword[t]
      sbb edx, dword[t+4]
      mov dword[t], eax
      mov dword[t+4], edx
    end;
    QueryPerformanceCounter( i2 );
    i2 := i2-i1;
    QueryPerformanceFrequency( i1 );
    Result := i2*1000000 div i1;
    Result := t/(Result);
    CPUFreq := Result;
    SetThreadPriority(GetCurrentThread,pr);
end;

procedure SetRealTime_;
var
   ProcessID : DWORD;
   ProcessHandle : THandle;
   ThreadHandle : THandle;
begin
  ProcessID := GetCurrentProcessID;
  ProcessHandle := OpenProcess(PROCESS_SET_INFORMATION,
        false,ProcessID);
  SetPriorityClass(ProcessHandle, REALTIME_PRIORITY_CLASS);
  ThreadHandle := GetCurrentThread;
  SetThreadPriority(ThreadHandle, THREAD_PRIORITY_TIME_CRITICAL);
end;

procedure SetNormalTime_;
var
   ProcessID : DWORD;
   ProcessHandle : THandle;
   ThreadHandle : THandle;
begin
  ProcessID := GetCurrentProcessID;
  ProcessHandle := OpenProcess(PROCESS_SET_INFORMATION,
        false,ProcessID);
  SetPriorityClass(ProcessHandle, NORMAL_PRIORITY_CLASS);
  ThreadHandle := GetCurrentThread;
  SetThreadPriority(ThreadHandle, THREAD_PRIORITY_NORMAL);
end;
@Ark
Apr 7 2017, 15:31
Цитата(Gruffly @ Apr 7 2017, 18:23) *
Учить, до посинения ...

Спасибо. А Вы не могли бы, кратко, своими словами, объяснить суть? sm.gif

Gruffly
Apr 7 2017, 15:39
Цитата(@Ark @ Apr 7 2017, 15:31) *
Спасибо. А Вы не могли бы, кратко, своими словами, объяснить суть? sm.gif

Что, именно?

Win-система позволяет управлять собой вплоть до кольца 0 (ring 0).
Любой поток(и) можно возвысить до статуса реал-тайм для выполнения некоторых time-замеров и вернуть его обратно, в normal-time.
Есть очень много тонкостей по замеру времени исполнения той или иной программы, того или иного участка ее.
Объяснить двумя словами - нереально.
Однако, начиная с WinNT - Windows может считаться реал-тайм системой, более того, есть специальные релизы ее.
Важно другое - что мы понимаем под реал-тайм?
Реал-тайм может быть жесткий, мягкий, промежуточный - все, от задач зависит.
Где-то ранее, я приводил реализацию большого проекта на WinNT - супервизорное управление технологическим оборудованием + управление электро-приводом.
Реализовано, более того - продано китайцам sm.gif
Эдди
Apr 7 2017, 15:55
Какой поток бреда!..
blackfin
Apr 7 2017, 16:07
Цитата(Эдди @ Apr 7 2017, 18:55) *
Какой поток бреда!..

Обычная в наших краях дуэль джентльменов на пенисах! biggrin.gif
Gruffly
Apr 7 2017, 16:12
Цитата(Эдди @ Apr 7 2017, 16:55) *
Какой поток бреда!..

Не спеши причислять себя к горным баранам, в горах их и без тебя хватает sm.gif
Using Windows NT for Real-Time Applications (Mitsubishi Electric Research Labs)
Нажмите для просмотра прикрепленного файла

@Ark
Apr 7 2017, 23:57
Цитата(Gruffly @ Apr 7 2017, 19:12) *
Using Windows NT for Real-Time Applications (Mitsubishi Electric Research Labs)
Нажмите для просмотра прикрепленного файла

Почитал. Может, что-то не так понял, но там говорится о временах порядка миллисекунд.
Вы выложили измерения в микросекундах... rolleyes.gif
Эдди
Apr 8 2017, 05:41
Даже из линукса при помощи rt- патча полноценной ртоси не получится! Что уж о пускалке игр говорить?
Gruffly
Apr 8 2017, 14:55
Цитата(@Ark @ Apr 8 2017, 00:57) *
Почитал. Может, что-то не так понял, но там говорится о временах порядка миллисекунд.
Вы выложили измерения в микросекундах... rolleyes.gif


Теперь по порядку:

Методы измерения времени на платформе Windows имеют свою историческую подоплеку:

1. timeGetTime() - возвращает время в ms, прошедшее с момента старта OS. Работает от мультимедийного таймера. Точность 1..5 ms.
2. GetTickCount() - возвращает время в ms, прошедшее с момента старта OS. Работает от того же таймера, но точность ниже (10..55 ms), т.к. срабатывает по прерываниям часов реального времени.
3. RDTS - чи­та­ет из про­цес­сор­но­го счёт­чи­ка чис­ло так­тов, про­шед­шее с мо­мен­та за­пус­ка про­цес­со­ра. Са­мый точ­ный счёт­чик из до­ступ­ных.
При частоте CPU = 3 GHz длительность тика составляет 1/3 = 0.33 нс.
Есть проблемы на современных платформах, связанные с изменением частоты процессора, переключением задачи между CPU в многопроцессорных и многоядерных случаях.
Проблемы не принципиальные, просто надо учитывать особенности применения rdts.
4. QueryPerformance­Counter() - «тай­мер вы­со­ко­го раз­ре­ше­ния».
Вве­дён фир­мой Microsoft, что­бы раз и на­все­гда по­ста­вить точ­ку в про­бле­мах из­ме­ре­ния вре­ме­ни.
Ча­сто­та это­го тай­ме­ра ( ~ 3 МГц и вы­ше) и не ме­ня­ет­ся во вре­мя ра­бо­ты си­сте­мы. Запрос частоты QueryPerfomanceFrequency().
Очевидно, что длительность тика составляет 1/3 = 0.33 мкс.

Методы превращения платформы Windows в реал-тайм OS (того или иного типа) тоже имеют свою историческую подоплеку:
1. Впервые это стало возможным после появления WinNT 3.1
2. Win2000 Advanced Server вполне претендовал на эту роль и использовался ( в т.ч. мной) для создания "мягких" реал-тайм приложений.
3. Были выпущены расширения для WinNT платформ.
Их много, наиболее известная - RTX от фирмы VenturCom (затем Ardence, затем куплена Citrix), сейчас подразделение Citrix выделилось в отдельную фирму IntervalZero Inc.
4. Microsoft всегда следила на требованиями embebbed-рынка.
Список специальных релизов реал-тайм Windows достаточно большой:

Windows 7 Professional for Embedded Systems and Windows 7 Ultimate for Embedded Systems
Windows Embedded POSReady 7
Windows Server 2008 R2 for Embedded Systems
Windows Embedded POSReady 2009
Windows Server 2012 R2 for Embedded Systems
System Center 2012 SP1
Windows Embedded Compact 2013
Windows Embedded 8.1 Industry
и более ранние + для мобильных девайсов.

Есть такое понятие, как время System-slice (SST). Это время переключения задач на той или иной платформе в многозадачных OS.
Для обычных реализаций Windows, значение SST составляет от 10 до 20 ms, для embedded - 1 ms, для расширений - менее 1 ms.
Именно это, в первую очередь, ограничивает диапазон применения любой многозадачной OS.
К измерениям времени на платформе имеет опосредованное отношение.

P.S.
Надеюсь, что ответил на вопросы.
@Ark
Apr 8 2017, 16:00
Цитата(Gruffly @ Apr 8 2017, 17:55) *
Надеюсь, что ответил на вопросы.

Да. Спасибо за информацию.
Эдди
Apr 8 2017, 16:19
Как вообще можно говно мастдайное как операционную систему рассматривать? Она же только для игрулек годится! И создавалась изначально как пускалка игр!!!
Gruffly
Apr 8 2017, 16:23
Цитата(Эдди @ Apr 8 2017, 17:19) *
Как вообще можно говно мастдайное как операционную систему рассматривать? Она же только для игрулек годится! И создавалась изначально как пускалка игр!!!

В горы вернись - там телескопы, звезды, инопланетяне и незамутненное сознание.
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Invision Power Board © 2001-2025 Invision Power Services, Inc.