Недавно, на одном из форумов, студент обратился за помощью для решения одной из тестовых задач - не за кодом, а именно за помощью в части идей ее решения.
Задачка простая:
- есть/создается массив random-целых (integer 32b) чисел;
- требуется отсортировать массив на месте или вывести на консоль по следующим правилам:
-- массив должен быть отсортирован так, чтобы слева от "центра" массива находились бы все четные числа по убыванию от начала к "центру", а справа - все нечетные по возрастанию от "центра" к концу массива.

( в кавычки взят "центр", поскольку центрирование случайных чисел - случайно ).

Пример (тест):
rnd= 19 [40,14,17,46,12,53,3,49,26,56,10,28,59,20,35,42,42,18,24]
sort=19 [56,46,42,42,40,28,26,24,20,18,14,12,10,3,17,35,49,53,59]

Требования: простота, изящность, самодокументируемость кода для понимания студентами.
Реализация планировалась на тех или иных разновидностях Pascal/Delphi/FreePascal/Lazarus.
О студенте быстро забыли и в междусобойчик вступили три программиста: двое предложили решения на Турбо-Паскаль в стиле Си, третий - в стиле ЯСВУ паскалевидного типа с использованием array.sort(cmp).

Предлагается профи решить эту студенческую задачку на любых ЯП, ЯВУ и ЯСВУ, с учетом требований.
Код должен быть приведен в полном объеме и с тестом.
Бонусом - эффективность исполнения (быстродействие).

P.S.
На том форуме было предложено много интересных решений, но все свелось, в конце концов, к array.sort(cmp), где cmp - лямбда функция.

program Project2;

{$APPTYPE CONSOLE}

{$R *.res}

uses
 System.SysUtils, Generics.Collections, System.Generics.Defaults, Math;

var
 a, b: TArray<Integer>;
 I: Integer;
begin
 a := [40,14,17,46,12,53,3,49,26,56,10,28,59,20,35,42,42,18,24];

 TArray.Sort<Integer>(a,
   TComparer<Integer>.Construct(
     function (const Left, Right: Integer): Integer
     begin
       if (Left mod 2 = 0) and (Right mod 2 = 0) then
         Result := CompareValue(Right, Left)
       else if (Left mod 2 = 0) and (Right mod 2 <> 0) then
         Result := -1
       else if (Left mod 2 <> 0) and (Right mod 2 = 0) then
         Result := 1
       else if (Left mod 2 <> 0) and (Right mod 2 <> 0) then
         Result := CompareValue(Left, Right);
     end));

 for I := 0 to High(a) do
   WriteLn(a[i]);

 ReadLn;
end.


То не студенты, то школьники.

что-вроде этого должно сработать:

function cmp(i1, i2: integer): integer;
const
 m=-MaxInt-1;
begin;
 i1:=i1 shr 1 xor i1 shl 31 xor m;
 i2:=i2 shr 1 xor i2 shl 31 xor m;
 if i1 xor i2>=0
 then i1:=i1-i2
 else i1:=i1 or 1;
 Result:=i1;  
end;


идея функции сравнения взята отсюда http://guildalfa.ru/alsha/node/20

Понятно, что школьники бывают уже не студентами, и студенты - еще и не школьники.

ДлиннО, не оптимально по коду, не показательно для стьюдентов.

Прошу, еще :)

Sha ©   (03.04.17 23:00) [2]

Ша, да я от тебя другого и не ожидал :)
Проверять не буду - это ваше дело.

Но! Стьюдентам это пока запредельно для понимания.
P.S.
Я не о тех, кто мировые олимпиады выигрывает, если - что.

Лямбду не увидел, пока.

Дам наводку:
- самый краткий вариант, в одну строку, получился на Питоне, но - в стиле Ша.
- самый краткий и понятный вариант, в две строки, получился на PascalABC.Net.

> Jeer ©   (03.04.17 23:03) [3]
>
> ДлиннО, не оптимально по коду, не показательно для стьюдентов.

Серьезно? Решение задачи с помощью 1 (прописью - одного) вызова функции сортировки с передачей туда функции сравнения - это длинно, не оптимально и не показательно?

> Jeer ©   (03.04.17 23:06) [5]
>
> Лямбду не увидел, пока.

Серьезно? А что же там в [1] такое?

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

Вот на JavaScript решение в одну строку

Kerk ©   (03.04.17 23:31) [7]
>>Серьезно? Решение задачи с помощью 1 (прописью - одного) вызова функции >>сортировки с передачей туда функции сравнения - это длинно, не оптимально >и не показательно?

> Лямбду не увидел, пока.
>>Серьезно? А что же там в [1] такое?

Лямдбу ты еще увидишь :)

>Вот на JavaScript решение в одну строку
>a.sort((a,b) => { /* сюда переписать мою лямбда-функцию с делфи */ });

Так возьми и перепиши, в соответствии с требованиями ТС.

Ладно, пока жду апологетов С, C++, С#, Phyton, Haskel, Ruby и даже Perl.

> Jeer ©   (03.04.17 23:43) [8]
>
> Так возьми и перепиши, в соответствии с требованиями ТС.

Это мне лень. Зачем переписывать то, что и так очевидно?

Если хочется извращений, они есть у меня. Вот другое решение на JS в одну строку (вместе с тестом получается три строки):



>node s.js
[ 56, 46, 42, 42, 40, 28, 26, 24, 20, 18, 14, 12, 10, 17, 3, 35, 49, 53, 59 ]

В сторону старой доброй функциональщины можно еще глубже покопать, но такие решения всегда будут менее читаемыми и менее очевидными, чем [1].

Или вот решение в 2 строки на JavaScript (вместе с тестом - 4). Желающие сэкономить место на экране могут в одну строку записать :)

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

var sort_funcs = [(a,b) => {return b-a}, (a,b) => {return -1}, (a,b) => {return 1}, (a,b) => {return a-b}]
var result = a.sort((a,b) => {return sort_funcs[a % 2 * 2 + b % 2](a, b)})

console.log(result)

По сути решение из [1], но чуть иначе записанное и без типизации, деклараций и бегин-ендов.

Все, хватит. Спать пора :)

Волшебная одна строка:




>node s3.js
[ 56, 46, 42, 42, 40, 28, 26, 24, 20, 18, 14, 12, 10, 3, 17, 35, 49, 53, 59 ]

program SortArray32;

{$APPTYPE CONSOLE}

{$R *.res}

uses
 System.SysUtils;

procedure Xchg(const i1, i2: pointer);
asm
 movd mm0, ebx
 movd mm1, ecx

 mov ebx, dword ptr [i1]
 mov ecx, dword ptr [i2]
 mov dword ptr [i2], ebx
 mov dword ptr [i1], ecx

 movd ebx, mm0
 movd ecx, mm1
end;

procedure FirstHigh(const i1, i2: pointer);
asm
 movd mm0, ebx
 movd mm1, ecx

 mov ebx, dword ptr [i1]
 mov ecx, dword ptr [i2]
 cmp ebx, ecx
 jge @@Ex //Если первое выше или равно, то ничего не делаем

 mov dword ptr [i2], ebx
 mov dword ptr [i1], ecx

@@Ex:
 movd ebx, mm0
 movd ecx, mm1
end;

procedure FirstLow(const i1, i2: pointer);
asm
 movd mm0, ebx
 movd mm1, ecx

 mov ebx, dword ptr [i1]
 mov ecx, dword ptr [i2]
 cmp ebx, ecx
 jle @@Ex //Если первое ниже или равно, то ничего не делаем

 mov dword ptr [i2], ebx
 mov dword ptr [i1], ecx

@@Ex:
 movd ebx, mm0
 movd ecx, mm1
end;

var
 a: array of integer;
 i, k: integer;
 OddIndex, EvenIndex: integer;
 LowestValue: integer;

begin
 try
   { TODO -oUser -cConsole Main : Insert code here }

   Randomize;
   SetLength(a, 40);
   for i := Low(a) to High(a) do a[i] := Random(100);

   Write('[');
   for i := Low(a) to High(a) do
   begin
     Write(IntToStr(a[i]));
     if i <> High(a) then Write(',');
   end;
   Write(']');
   Writeln;

   EvenIndex := 0;
   OddIndex := High(a);

   //Этап 1
   //Сортировка по четности
   while (EvenIndex < OddIndex) do
   begin
     //Если число нечетное, то сдвигаем в конец
     if ((a[EvenIndex] and 1) = 1) then
     begin
       Xchg(@a[EvenIndex], @a[OddIndex]);
       Dec(OddIndex);
     end
     else Inc(EvenIndex);
   end;

   //Выясним где граница
   if (a[EvenIndex] and 1) = 1 then Dec(EvenIndex);
   if (a[OddIndex] and 1) = 0 then Inc(OddIndex);

   //Этап 2
   //Сортировка четных со сдвигом к меньшему
   while (EvenIndex >= 0) do
   begin
     for i := 0 to (EvenIndex - 1) do FirstHigh(@a[i], @a[i + 1]);
     Dec(EvenIndex);
   end;

   k := High(a);

   //Этап 3
   //Сортировка нечетных со сдвигом к большему
   while (k <> OddIndex) do
   begin
     for i := (High(a) - 1) downto OddIndex do FirstLow(@a[i], @a[i + 1]);
     Dec(k);
   end;

   Writeln;
   Write('[');
   for i := Low(a) to High(a) do
   begin
     Write(IntToStr(a[i]));
     if i <> High(a) then Write(',');
   end;
   Write(']');
   Writeln;

   SetLength(a, 0);
   a := nil;

   Readln;

   asm
     emms
   end;

 except
   on E: Exception do
     Writeln(E.ClassName, ': ', E.Message);
 end;
end.


Кол-во элементов для сортировки: 100000
Время: 14,265 сек.

>dmk ©   (04.04.17 04:37) [13]
Круто..
До этого там никто не дошел :)

>Kerk ©   (04.04.17 01:51) [12]
Не выполнено основное условие - понятность для начинающего студента.

> Jeer ©   (04.04.17 09:50) [14]
>
> Не выполнено основное условие - понятность для начинающего
> студента.

Это еще в [1] выполнено :)

Ну ладно. Подождем посмотрим чего ж у нас нынче понятно начинающим студентаам :)

> Кол-во элементов для сортировки: 100000
> Время: 14,265 сек.


Чего так долго ?

>Чего так долго ?
С оптимизацией 64 бита - 8 секунд. Подумаю еще над оптимизацией. Попозже.

> dmk ©   (04.04.17 12:07) [18]
>
> >Чего так долго ?
> С оптимизацией 64 бита - 8 секунд. Подумаю еще над оптимизацией.
>  Попозже.

А смысл? Неужто есть надежда сделать быстрее квиксорта?

>Jeer ©   (03.04.17 21:59)

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);

> Kerk ©   (04.04.17 12:56) [19]
>> dmk ©   (04.04.17 12:07) [18]
>> С оптимизацией 64 бита - 8 секунд. Подумаю еще над оптимизацией.
> А смысл? Неужто есть надежда сделать быстрее квиксорта?

Разумеется, можно.
RadixSort в несколько раз быстрее, например, см. http://guildalfa.ru/alsha/node/21

> Сергей Суровцев ©   (04.04.17 13:21) [20]

Оригинально :)

>Kerk ©   (04.04.17 14:00) [22]
Главное - мгновенно и не зависит от ЯП.

> Сергей Суровцев ©   (04.04.17 14:15) [23]

Мне нравится. Но целых три строки, забракуют твое решение :)

>Kerk ©   (04.04.17 14:29) [24]
>Но целых три строки, забракуют твое решение :)
Ну реально, то строк две. ))

Зато:
>Требования: простота, изящность, самодокументируемость кода для понимания студентами.
>Бонусом - эффективность исполнения (быстродействие).

На самом деле студенту повезло, что препод дает такие задачи,
хоть тутошнему большинству они и кажутся детскими.

В последнее время все чаще приходится видеть студентов,
которые поменять 0 на 1 и обратно в один оператор без if не умеют.

А задачу замены 0->1->2->0 по кругу и задать-то некому )

> Сергей Суровцев ©   (04.04.17 14:51) [25]
>
> >Kerk ©   (04.04.17 14:29) [24]
> >Но целых три строки, забракуют твое решение :)
> Ну реально, то строк две. ))

Я все думаю как бы так записать код, чтобы избежать дублирования строк. Они же реально одинаковые. Но пока не придумал.

>Неужто есть надежда сделать быстрее квиксорта?
Всегда удивлялся таким вопросам. Его надо Джону Кармаку задать. Он будет на вас долго удивляться. Возможно зависнет ;)

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

Тупой как пробка код из [12] сортирует 100000 элементов за 0.12 секунды
Крутой ассемблерный код из [13] сортирует 100000 элементов за 18.5 секунды

Запускал на одном и том же ноутбуке для чистоты сравнения. Чтобы быть как Кармак, нужно думать как Кармак. А Кармак думает о практической необходимости и эффективности.

Ничего личного.

Я правильно понял, что по сути [13] - это по сути три сортировки пузырьком?

> Сергей Суровцев ©   (04.04.17 13:21) [20]


Не нашла в условии пункта, что исходный массив ПОЛОЖИТЕЛЬНЫХ чисел )))

Array.Sort(rnd);
i1=0;
i2=rnd.Length;
for (j  = 0; j < rnd.Length; j++)
if (rnd[j] % 2 == 0) begin sort[i1] = rnd[j]; i1=i1+1; end;
else begin sort[i2]=rnd[j]; i2=i2-1; end;

Очень понятно для студентов )))

Я из этой ветки одно понял. У всех людей очень разные критерии понятности :)))

Ну вот, народ подтянулся и есть оригинальные решения.

P.S.
В том нашем междусобойчике призерами стали:
- Phyton:
(здесь честная сортировка на месте )



- PascalABC.Net:
(здесь использовано разрешение сортировки при печати)

P.S.
И в том и в другом случае использованы лямбда-функции в строке.

То, что в итоге студент взял за основу себе - это максимально ему было понятно:

PascalABC.Net:
(алгоритм до предела понятен: четные вперед и две пузырьковые сортировки)

Kerk ©   (04.04.17 17:42) [30]
1. я не программист
2. это моя первая сортировка в жизни.
3. не надо ни кого унижать, всегда найдется чувак круче

dmk ©   (04.04.17 19:51) [37]
Не обижайтесь, в жизни всегда находятся те, кто хочет усесться на насесте и повыше, да еще и клушек под себя.
Таких мне жаль.

P.S.
То, что у Вас все получилось - это же отлично! Очередной небольшой шаг вперед и так всю жизнь, ибо иначе ты - обычный потребитель потребля-а.

> Jeer ©   (04.04.17 19:44) [34]
>
> rnd.sort(key=lambda x: -1*x if x & 0x1 else x, reverse=True)

Идея как у Суровцева, но как верно заметила manaka, в условии ничего не сказано о том, что числа только положительные. Так что это решение засчитать мы не можем :)

> здесь использовано разрешение сортировки при печати

Это вообще не решение. И сортировка не на месте, и сортированного массива на выходе нет.


> dmk ©   (04.04.17 19:51) [37]

Ты угадал выходит. См [36] :)
Студент не дурак. Решение хоть и не оптимальное, но хотя бы соответствует условиям задачи

Сергей Суровцев ©   (04.04.17 13:21) [20]
Да, Ваш вариант несомненно вошел бы в призеры.
Это и есть нестандартный подход к решению задач, что всегда высоко ценится.

Kerk ©   (04.04.17 20:03) [39]
Видишь ли, ты здесь не рефери.
см [38]

> Jeer ©   (04.04.17 20:05) [41]
>
> Kerk ©   (04.04.17 20:03) [39]
> Видишь ли, ты здесь не рефери.
> см [38]

Здесь не я рефери, здесь здравый смысл рефери. Условия задачи открыты каждому, ни одно из "решений" из поста [34] условиям не соответствует. Сочувствую.

Но я рад за студента. Он выбрал единственно верный вариант из предложенных.

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

Kerk ©   (04.04.17 20:08) [42]

Специально для тебя повторяю условия задачи:

- есть/создается массив random-целых (integer 32b) чисел;
- требуется отсортировать массив на месте или вывести на консоль по следующим правилам:
-- массив должен быть отсортирован так, чтобы слева от "центра" массива находились бы все четные числа по убыванию от начала к "центру", а справа - все нечетные по возрастанию от "центра" к концу массива.

Переработанный вариант от Суровцева для PascalABC.Net:
(ограничение - только ноль и положительные числа)

[codebox]
var
 ar: array of integer;
const
 maxValue = 60; // Max value of rnd
 maxLen = 19; // ar.Length

procedure Inv(ar: array of integer);
begin
 for var i := Low(ar) to High(ar) do
   if not Odd(ar[i]) then ar[i] := -ar[i];
end;

begin
// Init  
 SetLength(ar, maxLen);
 for var i := Low(ar) to High(ar) do
   ar[i] := random(MaxValue + 1);

 write('rnd= ', ar.Length,' ', ar);
 writeln();
 
 Inv(ar); ar.Sort(ar); Inv(ar);
 
 write('rnd= ', ar.Length,' ', ar);
 writeln();
end.

[/codebox]

O! codebox здесь не работает.. :(

P.S.
Красиво, что еще можно сказать.

> Jeer

На самом деле ограничения легко убираются:

 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;


В функцию Cmp из [2] вкралась ошибочка,
забыл учесть обратный порядок сортировки для четных.
Исправленая функция сравнения и несколько других до кучи:

const
 m=-MaxInt-1;

//неотрицательные числа: четные по возрастанию, затем нечетные по возрастанию
function Cmp1(i1, i2: integer): integer;
begin;
 i1:=i1 shr 1 xor i1 shl 31 xor m;
 i2:=i2 shr 1 xor i2 shl 31 xor m;
 if i1 xor i2>=0
 then i1:=i1-i2
 else i1:=i1 or 1;
 Result:=i1;
 end;

//неотрицательные числа: четные по убыванию, затем нечетные по возрастанию
function Cmp2(i1, i2: integer): integer;
begin;
 i1:=i1 shr 1 xor -(i1 and 1 xor 1);
 i2:=i2 shr 1 xor -(i2 and 1 xor 1);
 if i1 xor i2>=0
 then i1:=i1-i2
 else i1:=i1 or 1;
 Result:=i1;
 end;

//произвольные числа: четные по возрастанию, затем нечетные по возрастанию
function Cmp1a(i1, i2: integer): integer;
begin;
 i1:=i1 xor m; i1:=i1 shr 1 xor i1 shl 31 xor m;
 i2:=i2 xor m; i2:=i2 shr 1 xor i2 shl 31 xor m;
 if i1 xor i2>=0
 then i1:=i1-i2
 else i1:=i1 or 1;
 Result:=i1;
 end;

//произвольные числа: четные по убыванию, затем нечетные по возрастанию
function Cmp2a(i1, i2: integer): integer;
begin;
 i1:=(i1 xor m) shr 1 xor -(i1 and 1 xor 1);
 i2:=(i2 xor m) shr 1 xor -(i2 and 1 xor 1);
 if i1 xor i2>=0
 then i1:=i1-i2
 else i1:=i1 or 1;
 Result:=i1;
 end;

//произвольные числа по возрастанию
function Cmp0(i1, i2: integer): integer;
begin;
 if i1 xor i2>=0
 then i1:=i1-i2
 else i1:=i1 or 1;
 Result:=i1;
 end;


Ок, ты как и всегда - четок и краток, хотя и непонятен для начинающих студентов :)

> Kerk

Доморощенные функции могут быть не хуже библиотечных.

Скорость работы HybridSortSha_AII отсюда http://guildalfa.ru/alsha/node/10
сильно зависит от функции сравнения и пред/постобработки:
со сравнением Cmp2a: 100000 - 16мс, 1000000 - 172мс, 10000000 - 1856мс
с [48] и со сравнением Cmp0: 100000 - 16мс, 1000000 - 110мс, 10000000 - 1295мс

Скорость работы ShaRadixSort отсюда http://guildalfa.ru/alsha/node/21
гораздо выше и не зависит от функции получения ключа:
со функцией ShaRadixKeyJeer: 100000 - 0мс, 1000000 - 32мс, 10000000 - 265мс
с [48] и с функцией ShaRadixKeyInteger: 100000 - 0мс, 1000000 - 32мс, 10000000 - 265мс

ShaRadixKeyInteger есть по приведенной ссылке, а ShaRadixKeyJeer тут:

function ShaRadixKeyJeer(Item: pointer): integer;
begin;
 Result:=(integer(Item) xor m) shr 1 xor (-(integer(Item) and 1 xor 1)) xor m;
 end;


> Sha ©

Я не устаю удивляться твоей ловкости с битами. Никогда наверно не пойму как ты это делаешь :)

Допилил 64-битный вариант:

Всего элементов: 100000
Четных: 49836
Нечетных: 50164

Сортировка по четности: 0,001 сек.
Сортировка четных: 3,703 сек.
Сортировка нечетных: 3,547 сек.
Всего: 7,25 сек.

Возможно не самый быстрый и компактный вариант, зато не нагуглил ;)

program Sort64;

{$APPTYPE CONSOLE}

uses
 System.SysUtils, Windows;

var
 sA: uint64;
 //a: array[0..7] of integer = (50,62,31,45,41,85,70,75);

procedure SwapInt(const i1, i2: pointer);
asm
 .NOFRAME
 mov r9d, [i1]
 mov r10d, [i2]
 mov [i2], r9d
 mov [i1], r10d
end;

procedure DoHigh(EvenIndex: int64);
//while (EvenIndex >= 0) do
//begin
 //for i := 0 to (EvenIndex - 1) do FirstHigh(sA + (i shl 2));
 //Dec(EvenIndex);
//end;
asm
 .NOFRAME
 movq xmm0, rsi
 movq xmm1, rcx
 movq xmm2, rbx
 movq xmm3, rdx

 mov rsi, sA //Адрес первого элемента

 mov rbx, EvenIndex //while (EvenIndex >= 0) do
 cmp rbx, 1
 jl @@C //Пропусти значения меньше единицы, иначе нижняя граница превысит пределы
 dec rbx //Отнимаем идиницу, чтобы не превысить границу EvenIndex, т.к. [r11+4]

@@C: //while (EvenIndex >= 0)

 xor rcx, rcx //i := 0
 dec rcx

@@N:
 inc rcx

 mov r11, rcx //i = r11
 shl r11, 2
 add r11, rsi

 mov eax, [r11]
 mov edx, [r11+4]
 cmp eax, edx
 jge @@NP //Если первое выше или равно, то ничего не делаем

 mov [r11+4], eax
 mov [r11], edx

@@NP:

 cmp rcx, rbx
 jl @@N

 dec rbx
 cmp rbx, 0
 jge @@C  //while (EvenIndex >= 0) do

 movq rsi, xmm0
 movq rcx, xmm1
 movq rbx, xmm2
 movq rdx, xmm3
end;

procedure DoLow(OddIndex: int64; K: int64);
//while (k <> OddIndex) do
//begin
//  for i := OddIndex to (k - 1) do FirstLow(sA + (i shl 2));
//  Dec(k);
//end;
asm
 .NOFRAME
 movq xmm0, rsi
 movq xmm1, rcx
 movq xmm2, rbx
 movq xmm3, rdx

 mov rsi, sA //Адрес первого элемента

 mov rbx, OddIndex

 mov r8, K

@@C:
 mov rcx, rbx //for i := OddIndex
 dec rcx

 mov r10, r8 //to (k - 1)
 dec r10

@@N:
 inc rcx

 mov r11, rcx //i = r11
 shl r11, 2
 add r11, rsi

 mov eax, [r11]
 mov edx, [r11+4]
 cmp eax, edx
 jle @@NP //Если первое ниже или равно, то ничего не делаем

 mov [r11+4], eax
 mov [r11], edx

@@NP:

 cmp rcx, r10
 jne @@N

 dec r8 //Dec(K)
 cmp r8, rbx
 jne @@C

 movq rsi, xmm0
 movq rcx, xmm1
 movq rbx, xmm2
 movq rdx, xmm3
end;

procedure OutText(a: array of integer; H: integer);
var
 i: integer;

begin
 Write('[');
 for i := 0 to (H - 1) do
   Write(IntToStr(a[i]) + ',');
   Write(IntToStr(a[H]));
 Write(']');
 Writeln;
end;

var
 A: array of integer;
 NumElements, H, i: integer;
 OddIndex, EvenIndex: integer;
 ST, ET, ET1, ET2: cardinal;
 TT, TT1, TT2, TT3: double;
 DoOut: boolean;

begin
 //Кол-во элементов в массиве
 NumElements := 100000;

 //Флаг вывода текста
 if (NumElements > 40) then
   DoOut := false else
   DoOut := true;

 Randomize;
 SetLength(A, NumElements);

 H := High(A);
 for i := 0 to H do A[i] := Random(100);

 //Адрес первого элемента
 sA := uint64(@A[0]);

 //Вывод массива
 if DoOut then OutText(A, H);

 //Стартовые индексы
 EvenIndex := 0;
 OddIndex := H;

 ST := GetTickCount;

 //Этап 1
 //Сортировка по четности
 while (EvenIndex < OddIndex) do
 begin
   //Если число нечетное, то сдвигаем в конец
   if ((A[EvenIndex] and 1) = 1) then
   begin
     SwapInt(@A[EvenIndex], @A[OddIndex]);
     Dec(OddIndex);
   end
   else Inc(EvenIndex);
 end;

 //Выясним где граница
 if (A[EvenIndex] and 1) = 1 then Dec(EvenIndex);
 if (A[OddIndex] and 1) = 0 then Inc(OddIndex);

 //Вывод массива
 if DoOut then OutText(A, H);

 //Конец первого этапа
 ET1 := GetTickCount;

 Writeln('Всего элементов: ' + IntToStr(H + 1));
 Writeln('Четных: ' + IntToStr(EvenIndex + 1));
 Writeln('Нечетных: ' + IntToStr(H - OddIndex + 1));
 Writeln;

 //Этап 2
 //Сортировка четных со сдвигом к меньшему
 //Индекс должен быть боле нуля, т.к.
 //элементов для сравнения должно быть минимум 2
 if ((EvenIndex + 1) > 1) then DoHigh(EvenIndex);

 //Конец второго этапа
 ET2 := GetTickCount;

 //Этап 3
 //Сортировка нечетных со сдвигом к большему
 //Кол-во элементов для сравнения должно быть минимум 2
 if ((H - OddIndex + 1) > 1) then DoLow(OddIndex, H);

 //Конец последнего этапа
 ET := GetTickCount;

 //Засекаемый минимум
 TT := 0.001;
 TT1 := TT;
 TT2 := TT;
 TT3 := TT;

 if (ET - ST) > 0 then TT := ((ET - ST) / 1000);
 if (ET1 - ST) > 0 then TT1 := ((ET1 - ST) / 1000);
 if (ET2 - ET1) > 0 then TT2 := ((ET2 - ET1) / 1000);
 if (ET - ET2) > 0 then TT3 := ((ET - ET2) / 1000);

 //Вывод массива
 if DoOut then OutText(A, H);

 Writeln('Сортировка по четности: ' + FloatToStr(TT1) + ' сек.');
 Writeln('Сортировка четных: ' + FloatToStr(TT2) + ' сек.');
 Writeln('Сортировка нечетных: ' + FloatToStr(TT3) + ' сек.');
 Writeln('Всего: ' + FloatToStr(TT) + ' сек.');

 SetLength(A, 0);
 A := nil;

 Readln;
end.

> Kerk ©   (05.04.17 02:13) [52]
> Никогда наверно не пойму...

Заклинания настоящей магии тут https://graphics.stanford.edu/~seander/bithacks.html

P.S. Мир видится иначе сквозь призму графического адаптера )

> dmk

Есть несколько предложений по коду [53].

1. Флаг вывода текста можно вычислить без if:
DoOut:=(NumElements<=40);

2. Сортировка по четности будет работать быстрее и без лишних перестановок элементов,
если оба EvenIndex и OddIndex будут бежать навстречу друг другу,
ища элементы, которые надо переставить как в алгоритме быстрой сортировки QuickSort,
а затем переставлять их.

3. Скорость работы алгоритмов сортировки слабо зависит от языка (обычно не более 3 раз),
но сильно зависит от алгоритма (десятки и более раз).
Поэтому в первую очередь имеет смысл сосредоточиться на алгоритме.

4. Изучение и замеры скорости разнообразных опубликованных алгоритмов сортировки -
неиссякаемый источник вдохновления и грусти )

>Sha ©   (05.04.17 10:01) [55]
>2. Сортировка по четности будет работать быстрее
Это не самое узкое место: 100 млн за 0.6 сек.

>источник вдохновления и грусти
Просто выжал из этого алгоритма максимум. Думаю над другим.

> Всего элементов: 100000


> Всего: 7,25 сек.


Чего так долго ?

>Sha ©   (04.04.17 23:01) [48]
>На самом деле ограничения легко убираются:

Красиво! Практическая магия. ))
На Delphi работает идеально, а вот на C# не проканало...

Этот вариант, конечно попроще, но должен пройти на любом ЯП. ))




>Jeer ©   (04.04.17 21:36) [45]
>ограничение - только ноль и положительные числа

Ограничение на положительные снято. С нулем есть 2 варианта. Если не обрабатывать, он встанет ровно посередине между четными и нечетными. Можно и обрабатывать, сейчас он для примера закинут в ветку нечетных.

P.S.
В условиях говорится о массиве целых чисел, а не о целочисленном массиве. ))

Меньше циклов, веселее жизнь

           for (int i = 0; i < rnd.Length; i++)
           {
               if (rnd[i] < 0)
               {
                   if (rnd[i] % 2 == 0) rnd[i] = 1 / rnd[i];
                   else rnd[i] = 1 / rnd[i] * (-1);
               }
               if (rnd[i] % 2 == 0 && rnd[i] > 1) rnd[i] = rnd[i] * (-1);
               if (rnd[i] == 1) rnd[i] = rnd[i] + 0.1;
               if (rnd[i] == 0) rnd[i] = 1;
           }
           Array.Sort(rnd);
           for (int i = 0; i < rnd.Length; i++)
           {
               if (rnd[i] % 2 == 0 && rnd[i] < -1) rnd[i] = rnd[i] * (-1);
               if (rnd[i] < 0 && rnd[i] > -1) rnd[i] = 1 / rnd[i];
               if (rnd[i] > 0 && rnd[i] < 1) rnd[i] = 1 / rnd[i] * (-1);
               if (rnd[i] == 1) rnd[i] = 0;
               if (rnd[i] == 1.1) rnd[i] = 1;
           }


Сергей Суровцев ©   (06.04.17 14:23) [59]
Оригинально, но не спортивно.

>Jeer ©   (06.04.17 22:13) [60]
>Оригинально, но не спортивно.

Почему?

>Jeer ©   (06.04.17 22:13) [60]

Как по мне, так вот это не спортивно: )))

>отсортировать массив на месте или вывести на консоль

Потому что это две принципиально разные по сложности задачи.

Сергей Суровцев ©   (07.04.17 00:59) [62]

Задача была дана на откуп студентам разного уровня подготовки - кто на что был горазд, тот так и смог реализовать.
Можно дать задачу, с которой справятся 5% студентов. Что делать с остальными? Отсеивать? А можно дать варианты и там будет уже 50% удачных решений.

Еще раз, задача была дана для обычных студентов, не софт-маньяков :)

>Jeer ©   (07.04.17 01:03) [63]
>Еще раз, задача была дана для обычных студентов, не софт-маньяков :)

В те времена, когда описания ЯП умещалось в брошюру, а алгоритмы сортировки массивов писались вручную вариант вывода на консоль имел хоть какой-то образовательный смысл. А сейчас его образовательная нагрузка просто отделить четные от нечетных в разные массивы (для этого варианта в условии это разрешается) и вызвать две стандартные сортировки.
А там где программирование - основной профиль обучения студенты и должны быть главными софт-маньяками. ))

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

>Sha ©   (07.04.17 10:30) [65]
>На мой взгляд, в этой задаче условие "или вывести на консоль" создает лишнюю лазейку.

Вот и я о том же. ))

>Sha ©

А почему та красота из

>Sha ©   (04.04.17 23:01) [48]

для C# не сработала? Сдвиг через минус в Delphi и С# по разному обрабатывается?

нужно использовать беззнаковый сдвиг вправо >>>

> [64] Сергей Суровцев ©   (07.04.17 10:07)
> А сейчас его образовательная нагрузка просто отделить четные
> от нечетных в разные массивы

Я может что-то не понял в твоём высказывании, но как же фундаментальные знания против сугубо цеховых навыков?

> Сергей Суровцев ©   (07.04.17 10:07) [64]
> А там где программирование - основной профиль обучения студенты
> и должны быть главными софт-маньяками. ))

Кстати, да. Я сейчас методику Sha еле-еле понимаю, но когда был студентом, понял бы. Это сейчас я далек от этого, но тогда все эти битовые операции и разные формы представления чисел были обыденностью. То же самое с алгоритмами. Через 15 лет половина конечно выветрится из головы, но прямо сейчас-то у них кругозор должен быть ого-го.

>Inovet ©   (07.04.17 12:25) [69]

Почему "фундаментальные знания" должны быть против "сугубо цеховых навыков"? )))

> [71] Сергей Суровцев ©   (07.04.17 13:15)

Потому что цеховые навыки могут не коррелировать с фундаментальными знаниями. Можно уметь что=-то сделать, чтобы работало, но не понимать, почемк оно работает. Разве с таким не сталкивался?

>Sha ©   (07.04.17 12:18) [68]
>нужно использовать беззнаковый сдвиг вправо >>>

Нету его...

Оператор Java, который недоступен в C#, это оператор сдвига (>>>). Этот оператор используется в языке Java из-за малого числа в нем беззнаковых переменных для случаев, когда требуется смещение вправо для вставки 1 в наиболее важные разряды.
Язык C# поддерживает беззнаковые переменные, поэтому в C# требуется только стандартный оператор >>. Данный оператор выдает различные результаты в зависимости от того, имеет операнд знак или нет. При сдвиге вправо беззнакового числа в самый важный бит вставляется 0, а при сдвиге вправо числа со знаком выполняется копирование предыдущего самого важного бита.

использовать явное преобразование, что-нибудь вроде (uint)Arr[i],
и маску m тоже сделать беззнаковой

>Sha ©   (07.04.17 14:01) [74]

Ну да, так в итоге и сделал в обход отсутствия >>>.

>Sha ©   (07.04.17 10:30) [65]
>
>На мой взгляд, в этой задаче условие "или вывести на консоль" создает лишнюю >лазейку.
>Например, можно за каждый проход по массиву находить только одно >подходящее число и выводить его.

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

А дипломы потом все одинаковые получат. Беда все-таки у нас с образованием в IT... Профнепригодные преподаватели вместо того, чтобы научить чему-то студентов дают им задачи попроще.

Для сравнения дам задачу из вводного курса в программирование одного из больших западных вузов.

Сколькими способами можно разменять сумму в 1 доллар, если имеются монеты по 50, 25, 10, 5 и 1 цент? У этой задачи есть простое решение в виде рекурсивной процедуры.

Эта задача не сложная. Но между ней и "покажи, что умеешь выводить массив на консоль" - пропасть.

Для сравнения могу предложить решить на Delphi какую-нибудь задачу из "Этюдов для программиста" Уэзерелла.

> Игорь Шевченко ©   (07.04.17 20:05) [79]
>
> Для сравнения могу предложить решить на Delphi какую-нибудь
> задачу из "Этюдов для программиста" Уэзерелла.

Предложите

Игорь Шевченко ©   (07.04.17 20:05) [79]
Ох, Игорь - хватаю за палец.

Charles Wetherell, Prentice-Hall Inc, 1978

Глава 15, стр. 80.
"Поиск узоров из простых чисел".

Jeer ©   (07.04.17 19:32) [76]
>Еще раз - надо всем возможность реализовать себя.

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

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

> Сергей Суровцев ©   (08.04.17 19:21) [82]
>
> Jeer ©   (07.04.17 19:32) [76]
> >Еще раз - надо всем возможность реализовать себя.
>
> Возможность реализовать себя нужно давать всем, но в рамках
> выбранной профессии. Если такая реализация затруднительна,
>  есть две возможности - упереться рогом, вникнуть и решить
> задачу, втянуться или сменить направление и реализовывать
> себя в какой-то другой области, если эта не вызывает азарта
> и интереса.

+1

Один мой знакомый работал учителем в американской муниципальной школе. Они там для повышения успеваемости (а от этого зависит финансирование) тем, кто не справлялся с контрольными, давали другую контрольную с упрощенными задачами. Этот путь предлагает Jeer. Но по-моему это ерунда какая-то.

Удалено модератором

Удалено модератором

Удалено модератором

Удалено модератором

Удалено модератором

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

Добавил эту задачу и частично ее решение сюда http://guildalfa.ru/alsha/node/20

> в свое время до финалов всероссийских олимпиад доходил

Я, кстати, чтоб ты не думал, что я хвастаюсь, искренне верю, что это не потому, что я такой умный, а потому что средний уровень образования в IT такой какой он есть. Интересуйся немножко профессией и всё, ты уже как минимум один из лучших студентов потока.

Я вот недавно с коллегой обсуждал языки программирования. Спрашиваю у него между делом, знает ли он что такое lexical scope. Он мне такой: да, конечно. А я думаю: вот я дурак, зачем глупости спрашиваю. А потом понял, что не привык, у нас-то и преподаватели программирования далеко не все знают, что это такое. И даже статью на русском языке в википедии на эту тему нормальную некому написать.

Удалено модератором

Удалено модератором

Удалено модератором

Kerk ©   (09.04.17 01:09) [89]


> Вот кстати подход "сделайте решение как можно более хитровывернутым",
>  


Видимо мне попадались другие преподаватели, я никогда не слышал, чтобы выдвигались такие требования :)
Люди обычно сами пытаются вывернуться, обычно же, для самоутверждения или чтобы попробовать какую-то неизученную область используемого средства.

> Игорь Шевченко ©   (09.04.17 10:25) [95]
>
> Kerk ©   (09.04.17 01:09) [89]
>
> > Вот кстати подход "сделайте решение как можно более хитровывернутым",
>
> Видимо мне попадались другие преподаватели, я никогда не
> слышал, чтобы выдвигались такие требования :)

Если ты про тех преподавателей, что тебя учили, то я не знаю. Я то время не застал. Если ты про сейчас, то посмотри хотя бы на эту ветку. Понятно, что напрямую никто не говорит. Но что декларируется как добродетель? "У нас есть решение в одну строку, и в две строки". Тебя в реальной работе волнуют такие вопросы?

Вижу удаленные посты. Я спровоцировал, это моя вина. Есть исключения конечно из того, о чем я так резко высказался. Я бывал, например, на лекциях в ИТМО и ПОМИ РАН тут в Питере. Очень серьезный уровень. И Jeer сейчас будет плеваться, но они даже не гнушаются приглашать иностранных гуру образования в этой сфере. Но таких ИТМО у нас мало, а jeerовских заборостроительных, где снижают сложность заданий, чтобы каждому дать шанс получить диплом - много. И это вот и печально.

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

Kerk ©   (09.04.17 13:27) [96]


> Но что декларируется как добродетель? "У нас есть решение
> в одну строку, и в две строки". Тебя в реальной работе волнуют
> такие вопросы?


Меня в реальной работе волнует наиболее понятный код, при всем прочем равном отдается предпочтение решению минимальным числом операторов.


> то посмотри хотя бы на эту ветку


Так тут понты в основном.

Удалено модератором

Игорь Шевченко ©   (09.04.17 14:12) [97]
> Меня в реальной работе волнует наиболее понятный код,

А меня - рабочий, безглючный, удовлетворяющий условиям ТЗ. Как и чем и кем он написан - пофиг.

kilkennycat ©   (09.04.17 15:09) [99]

Займись командной разработкой, придешь к моей точке зрения.

Удалено модератором

Удалено модератором

Kerk ©   (09.04.17 13:27) [96]
> снижают сложность заданий, чтобы каждому дать шанс получить
> диплом

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

Поясню. Здесь уже не раз обсуждался тест, которым я пользовался для отбора соискателей. Задачи в этом тесте имели разную сложность и были сгруппированы по областям (знание языка, знание VCL, знание WinAPI и пр.). Это давало возможность выяснить, что именно соискатель знает хорошо, а что - плохо.

Так вот - если даже человек хорошо знал всего лишь одну область, но в данный момент именно такой человек нам и был нужен, то он проходил (по крайней мере, на испытательный срок). Остальному научим - но уже в процессе.

> kilkennycat ©   (09.04.17 15:09) [99]

> А меня - рабочий, безглючный, удовлетворяющий условиям ТЗ.
> Как и чем и кем он написан - пофиг.

Костя, а давай сыграем в ролевую игру?
:o)

Ты тестируешь соискателя и даешь ему такую задачу: если целочисленная переменная X равна 1, то присвоить ей значение 0, а если она равна 0, то присвоить ей значение 1.

Соискатель пишет:
X := 1 - X;

Твои условия выполнены: код рабочий, безглючный и удовлетворяет ТЗ.

Что скажешь?

> kilkennycat ©   (09.04.17 15:09) [99]
>
> Игорь Шевченко ©   (09.04.17 14:12) [97]
> > Меня в реальной работе волнует наиболее понятный код,
>
> А меня - рабочий, безглючный, удовлетворяющий условиям ТЗ.
>  Как и чем и кем он написан - пофиг.

Завтра тебя попросят новую фичу добавить или старую переделать и сразу станет не пофиг, кем и как написан код :)

По-моему, всё искусство программирования состоит в том, чтобы находить простые решения для сложных проблем. Когда запутанную задачу правильно разобьешь на небольшие части, кусочки сами собой собираются в паззл. И потом уже кажется, что иначе и быть не могло. Каждый элемент решения крайне прост и даже очевиден, но все вместе они составляют требуемую картину.

Не раз меня спасало это вот интуитивное чувство. Если делаешь что-то сложное, что-то здесь не так, стоит еще раз подумать.

>  Юрий Зотов ©   (09.04.17 17:57) [103]

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

> Kerk ©   (09.04.17 19:02) [105]

> По-моему, всё искусство программирования состоит в том,
> чтобы находить простые решения для сложных проблем.

Согласен, но добавлю свои 5 копеек: "А также в том, чтобы эти решения предусматривали простое изменение и/или расширение функционала без серьезного перепахивания кода и без риска поломать функционал в другом месте кода".

> Игорь Шевченко ©   (09.04.17 16:41) [100]
> Займись командной разработкой

уже и в разных ролях.


> Юрий Зотов ©   (09.04.17 18:12) [104]
> X := 1 - X;
> Твои условия выполнены: код рабочий, безглючный и удовлетворяет ТЗ.
> Что скажешь?

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


> Kerk ©   (09.04.17 19:02) [105]
> Завтра тебя попросят новую фичу добавить или старую переделать
> и сразу станет не пофиг, кем и как написан код :)

Естественно, код должен комментироваться. Это хоть и немного не вписывается в "пофиг", но это ж совсем базовые вещи.
Кроме того, новая фича - это новое ТЗ. Это другая задача, другая оплата.

Вы как-то упускаете при рассуждении бизнес-сторону.
Да, здорово, конечно, быть офигенным программистом, находящим моментально самые идеальные решения, да еще легко изменяемые в будущем при требовании каких-то фич.
Но не все такие. Я точно не такой, идеальное решение найти могу, но моментально - нет. И от меня заказчик требует программу (вот, пока писал это - в очередной раз напомнили о сроках) вовремя и работающую. И что там внутри, да хоть if (x == 1) then x = 0 else x = 1 написано - это ему пофиг.

> kilkennycat ©   (09.04.17 19:52) [108]

Увы, Костя, проблемы предвидятся. Через полгода безукоризненной (якобы) эксплуатации программы клиент вдруг присылает тебе скрытую и случайно обнаруженную им ошибку: некая величина Z должна быть равна 100, а программа молча пишет 200 и не выдает никаких ошибок. Причем выясняется, что программа глючила все эти полгода (только этого никто на замечал) и из-за этого клиент потерял кучу бабла.

Ты начинаешь разбираться и через несколько бессонных суток находишь, что X := 1 - X иногда работает неверно. Потому что X, оказывается, иногда бывает равен и не 0, и не 1. Через неделю упорных поисков выясняется, что кто-то когда-то что-то неверно забил в БД и концов уже не сыскать. Заказчик матерится, ты нервничаешь, дальнейшее сотрудничество под вопросом.

А между тем, по-настоящему грамотный разработчик, получив такое ТЗ должен был либо его уточнить (что делать, если X не 0 и не 1 ?), либо вместо X := 1 - X написать что-то типа этого:

if X = 0 then
 X := 1
else
 if X = 1 then
   X := 0
 else
   raise MyException.Create('Внятное сообщение об ошибке');

Как минимум, ошибка всплыла бы при первом же своем проявлении, заказчик сохранил бы кучу бабла, а ты сохранил бы кучу нервов и времени.

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

> Юрий Зотов ©   (09.04.17 20:25) [109]

нечестно. ты сказал, "если целочисленная переменная X равна 1, то присвоить ей значение 0, а если она равна 0, то присвоить ей значение 1"
Здесь не указано третье состояние, не указаны возможные значения входных данных, зато сказано, что это решение работает безглючно. а теперь вдруг глючно.
Так что, глючное тз = глючный результат.

истина где-то в районе 100500-го поста

> ухты ©   (09.04.17 20:32) [110]
>
> это правильно, сначала подсказать решение, потом добавить
> условия, базы притянуть, кривые руки и т.п. а в итоге с
> умным видом осудить

Ну это был предсказуемый ход со стороны ЮЗ. Но ведь в жизни так и бывает.

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

Можно даже усложнить, перемешав результаты первого семестра. Чтобы переделывать пришлось не свою программу, а чужую. Но это совсем жестко :)

Студенты во время учебы пишут всё с нуля. Лабораторные, курсовики, диплом. А потом приходят на работу и проваливаются по уши в миллионы строк чужого кода 15летней давности. Но откуда навыку работы с чужим старым кодом взяться? Набивают шишки в процессе работы уже.

> Kilkennycat ©   (09.04.17 20:54) [111]

Костя, пример, конечно, несколько притянут за уши, но все же показывает, что не все равно, кто и как пишет код. Опытный зубр, сразу предвидя ситуацию и, закладываясь на возможные ошибки в ТЗ и в данных напишет не "элегантный" короткий вариант, а "тупой" трехэтажный  IF с выдачей сообщения.

> Юрий Зотов ©   (09.04.17 21:38) [114]

даже страшно представить, что творится внутри OC, написанной опытными зубрами... )

> Юрий Зотов ©   (09.04.17 21:38) [114]

Опытный зубр уточнил бы ТЗ. вплоть до "а точно ли нужна целочисленная, если у нее именно такие состояния".
А если опытный зубр напишет с MyException.Create('Внятное сообщение об ошибке');, то во-первых, он частично нарушил тз, так как там не требовалось этого, во-вторых, возможно сделал лишнюю работу (ведь вполне возможно, что х никогда не примет значения иные, чем 0 и 1), в-третьих, о этой лишней работы проделает офигенно много, поскольку начнет писать на каждый чих.
Ну и мне кажется, что опытный зубр, которого уже достало глючное, непонятное, неполное и фантастическое тз, написал бы что-то вроде x = x > 0?0:1;

> Sha ©   (09.04.17 21:44) [115]

> даже страшно представить, что творится внутри OC, написанной
> опытными зубрами... )

Внутри OC, написанной опытными зубрами творится ожидание 100500-го сервиспака. И это еще хорошо.
:o)

> Kilkennycat ©   (09.04.17 22:02) [116]
> написал бы что-то вроде x = x > 0?0:1;

x:=ord(x=0);

> x = x > 0?0:1;
x = x != 0?0:1; ))

Всего предвидеть не может никто. Какими бы опытными зубры не были :)

Именно поэтому читаемость и легкость сопровождения важнее хитровывернутости :)

> x = x > 0?0:1;
> x:=ord(x=0);
> x = x != 0?0:1;

А вот все эти варианты как раз и недопустимы. В ТЗ не сказано, что делать, если X не 0 и не 1. Поэтому надо либо уточнять ТЗ, либо выдавать ошибку - но ни в коем случае нельзя расширять неполное ТЗ своими догадками. Иначе запросто можем получить, что программа работает неверно, но никто этого не замечает.

> В ТЗ не сказано, что делать, если X не 0 и не 1.
так и не писали бы никаких исключений, тоже было бы тихо-нерабоче.
самим можно, а нам низя, не интересно так

ухты ©   (09.04.17 22:11) [119]
> x = x != 0?0:1;

да, в некоторых компиляторах так будет шустрее.

> Юрий Зотов ©   (09.04.17 22:22) [121]
> но ни в коем случае нельзя расширять
> неполное ТЗ своими догадками. Иначе запросто можем получить,
>  что программа работает неверно, но никто этого не замечает.

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

> Kilkennycat ©   (09.04.17 22:37) [124]

Для чего ж тогда вообще нужны исключения?

> Kerk ©   (09.04.17 22:40) [125]

ну, лично я стараюсь их использовать как можно меньше и в случаях, когда рискую получить что-то форсмажорное, например, при получении данных из сети.

> Kilkennycat ©   (09.04.17 22:37) [124]

> выдача исключения - точно такое же расширение ТЗ.

Нет. В ТЗ не сказано, что надо делать - вот программа ничего и не делает. В полном соответствии с ТЗ.

> наши варианты позволят программе, возможно, и при неверных
> входных данных продолжить функционирование

Ты изменишь свое мнение, когда программа, молча продолжив свое функционирование, насчитает тебе отрицательную зарплату.

исключения это просто оптимистик, и всего то )

> Юрий Зотов ©   (09.04.17 22:47) [127]

вполне возможно, что она насчитает мне в 10 раз больше )

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

> Kilkennycat ©   (09.04.17 22:37) [124]

> наши варианты позволят программе, возможно, и при неверных
> входных данных продолжить функционирование

Кто сказал, что при возникновении исключения программа непременно должна завершаться?

Она должна прервать заведомо неверную операцию, сообщить об этом юзеру, восстановить свое правильное состояние и продолжить работу. А завершиться она должна лишь при невозможности продолжения.

> Юрий Зотов ©   (09.04.17 22:56) [130]

ну, согласен. Но это лишь подтверждает, что на ту задачу ТЗ неполное, и любой ответ - верен.

я таких неполных задач тоже могу назадавать.
например: есть массив байтов, размер массива 3. присвоить каждому элементу 1.

> Kilkennycat ©   (09.04.17 23:03) [131]

а, ну и дополню, что испытуемый написал:
a[0] = 1;
a[1] = 1;
a[2] = 1;

Берем такого на работу? :)

тут одного зубра мало, тут помощник нужен

> Kilkennycat ©   (09.04.17 23:06) [132]

> Берем такого на работу? :)

Не берем. Он не предусмотрел, что завтра размер массива может измениться и что его индекс не обязан начинаться с нуля.

> Юрий Зотов ©   (09.04.17 23:15) [134]

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

студентам прием на работу не светит

> Sha ©   (09.04.17 23:26) [136]

большинству студентов - да. Но из моего опыта их тестирования, меньшее свечение им давали амбиции - ЗП хотят как у зубра.

> PIC10F200 обладает всего 352 байтами

384. память моя никчерту стала. пить, что ли, меньше надо?

> Sha ©   (09.04.17 23:26) [136]

Как-то шеф мне говорит: "Пойдем, прособеседуем одного человека, к нам на должность аналитика хочет. Два дня назад он уже приходил и получил задачку: нарисовать структуру простейшей БД для библиотеки. На нее он запросил 2 дня, вот сегодня и принес".

Ок, идем. Сидит молодой парнишка, вчерашний студент. Смотрим его творение. Там таблица книг и таблица авторов. Связка - один к одному.

Спрашиваем: а может быть несколько разных авторов у одной и той же книги?
- Да, отвечает.
- А может один и тот же автор написать несколько разных книг?
- Да.
- Значит, какая должна быть связка?

Молчит. Подсказываем: многие ко многим. И спрашиваем - а как ее реализовать? Снова молчит.

Блин! Окончил ВУЗ по специальности. Запросил 2 дня на задачку, которая набрасывается за 15 минут. Претендует на аналитика. Ну и как его брать?

Но самая распространенная ошибка студентов - это, наверное, тихое гашение исключений (это же хорошо, когда программа работает без ошибок).

а зачем подсказывать на собеседовании?

> Юрий Зотов ©   (10.04.17 00:23) [139]

бд для библиотеки, на самом деле, не такая уж простая задачка...  за 15 минут вряд ли набросаешь.

> Kilkennycat ©   (10.04.17 00:39) [141]

Костя, а лошади едят траву?
:o)

> ухты ©   (10.04.17 00:35) [140]
>
> а зачем подсказывать на собеседовании?

Чтоб посмотреть на дальнейший ход мысли.

> Юрий Зотов ©   (10.04.17 00:45) [142]
> Костя, а лошади едят траву?

у меня настолько плохая память, что вот помню, что ты такой вопрос задавал, но опять не помню, к чему и почему :(

Ну а библиотечное бд я ща по-тихоньку мучаю, так там столько всякого... с одними стандартами библиотечной каталогизации разбирался несколько дней.

Ну понятно же, что никто не ждет промышленного качества библиотечную БД за 15 минут. Такие задания обычно нужны просто чтоб было о чем на собеседовании поговорить.

на аналитика и многие ко многим надо подсказывать, чтобы поговорит? ))
вообще не уверен стоит ли в принципе подсказывать (вообще звучит странно), а тут еще и такие мелочи.

>Юрий Зотов ©   (10.04.17 00:23) [139]
>Но самая распространенная ошибка студентов - это, наверное, тихое гашение >исключений (это же хорошо, когда программа работает без ошибок).

Почему я люблю Delphi - это как раз реакция на ошибки.
Delphi использует механизм исключений, С-Windows - механизм кодов ошибок.

> насчитает тебе отрицательную зарплату.

Кстати, это не выдумка, а совершенно реальный случай.

Швейное объединение "Сокол", конец 80-х годов. Есть справочник операций. В нем сказано, что операция X стоит Y копеек - и так по всем операциям. Ежедневно в БД забивается, сколько каких операций выполнил работник-сдельщик, а в конце месяца идет расчет зарплаты.

И вдруг месячная зарплата иногда получается отрицательной. Бухгалтерия вопит, что срок прошел, а она не может начислить зарплату сдельщикам (которых сотни). Начальник ВЦ ругается и грозит лишить девчонок-операторш либо премии, либо девственности, либо сразу жизни. Девчонки плачут и клянутся, что все забили правильно.

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

Проблема была устранена заменой Integer на Real. Но если бы программа сразу контролировала, что она считает чушь и выдавала ошибку, то все было бы гораздо проще, быстрее и без нервотрепки.

а у мня был обратный случай: бухгалтерия звонит и вопит, что пенсионные отчисления списались дважды, караул! Ну, посмотрел тут же конфиг 1С, всё гуд, дважды невозможно, отчитываюсь: ищите лишнюю проводку. в принципе, рядовая ситуация, когда штат бухгалтерии раздут, главбух как начальник не ахти, кто че делает непонятно, в последний день и т.д.  Одному трижды три сотрудницы начислят, другому ни разу ни одна.
Но главбух вопит: "быть такого не может, мы умные, а ты дурак".
Разумеется, нашли лишнее позжее, свалили на какю-то молодую бухгалтершу, самую безропотную, наверное.
Так что,

> все было бы гораздо проще, быстрее и без нервотрепки.

после первого же случая ошибки, если бы люди (и программисты и пользователи) были разумны, спокойнее и адекватнее,а не вопили "я - самый умный, у меня ошибки быть не может!"

> ухты ©   (10.04.17 02:46) [146]
>
> на аналитика и многие ко многим надо подсказывать, чтобы
> поговорит? ))

А там аналитик был? Тогда хз :)

---
По поводу багов был забавный случай давно. Мы тогда с энергосбытом работали. Внедрялись в маленьком городке Самарской области. Аналитики сначала приехали посмотреть что да как. Выяснили, что у них по тарифам за первые 50кв*ч (цифры условные) пенсионеры платят 50%. Местные бухгалтера решили, что 50% скидка на 50кв*ч - это все равно что 100% скидка на 25кв*ч, ну и считали так. Они были почти правы, но не совсем. Ведь если допустим пенсионер потратил 30кв*ч, то по тарифу должен заплатить как за 15, а по формуле местных бухгалтеров получится только 5.

В общем, интересный был случай. Про нас тогда даже в местной газете писали. Что лишаем пенсионеров льгот :)

>Юрий Зотов ©   (09.04.17 20:25) [109]
>А между тем, по-настоящему грамотный разработчик, получив такое ТЗ должен был либо его уточнить (что делать, если X не 0 и не 1 ?)

Разработчик любой грамотности уточняет ТЗ только там где есть противоречия и вариантность.
Если ему дали ТЗ, в котором четко 2 варианта, он его и реализует. Оптимальным образом. Если в итоге выясняется, что это НЕ ТОЛЬКО 2 ВАРИАНТА,
то проблема не в разработчике, а в анализе задачи и продуманности ТЗ. Просто у нас все любят валить на того кто последний в цепочке. Он, дескать
должен за всеми все проверять. А вот нифига не должен. И за этот косяк получить должен был не программист, а тот кто ставил для него задачу.
Программист, особенно в команде, может вообще не знать откуда берутся данные для его куска кода и куда они пойдут дальше. Его дело - решить
поставленную ЕМУ задачу в рамках поставленного ЕМУ ТЗ.
Кстати та же фигня и с INT. Еще на стадии проектирования нужно было иметь ввиду возможность такого косяка. И избежать его В ПРИНЦИПЕ, а не
пытаться делать сотни проверок - не вылетело ли сейчас это из диапазона.
Просто всем и всегда удобно свалить все на этап реализации - мы тут В ЦЕЛОМ подумали, а всякие мелочи, это вы там сами.

> Сергей Суровцев ©   (10.04.17 14:15) [151]

Все верно, но это в теории. А на практике так: "мы тут В ЦЕЛОМ подумали, а всякие мелочи, это вы там сами".

Хорошо вам. Я с 2006 года никаких ТЗ не видел. Agile, все дела... :)

> Kerk ©   (10.04.17 14:31) [153]

Несколько последних лет я их тоже не видел, а только слышал. Постановка задачи "в простой устной форме" или "Agile по-русски". И чуть что - постановщик от своего же косяка отмазывается - мол, "я этого не говорил".

>Юрий Зотов ©   (10.04.17 14:29) [152]

Вот есть, к примеру БД. В ее таблице поле, где теоретически 2 значения 0 и 1. Естественно проверка идет а=1, а=0. Если в таблицу попадет а=3, строка не зацепится никогда.
Смысл в том, чтобы строить проверки подобного не на уровне кода - возможно кто-то когда-то кривыми руками чего внесет, а на уровне периодического теста к БД, и скопом проверять ВСЕ возможные отклонения от нормы и их исправлять.
Именно это нужно было в примере с "х=х-1". То есть подтягивать входные данные к заявленным в ТЗ, а не пытаться в программе предусмотреть ВСЕ возможные неадекватности этих данных. В первом случае задача конечна и решаема, причем единоразово и с гарантией. Во втором задача решается постоянно и в результате лишь приближение к правильности, а гарантии нет никогда.

"а еще боремся за звание дома высокой культуры быта" )

> Сергей Суровцев ©   (10.04.17 14:46) [155]

Конечно, такие ограничения надо закладывать на уровне БД - уже хотя бы для того, чтобы никаким "левым" клиентом нельзя было нарушить правильность данных.

Это азбука, и она правильная. А на практике было вот что:
- триггеры запрещены;
- хранимки запрещены;
- внешние ключи запрещены (они, конечно, есть, но БД об этом не знает);
- нормализация данных близка к нулю;
- и т.п.

Понадобилось как-то раз добавить в таблицу автовычисляемое поле, а по нему - индекс. Месяц доказывал, что это безопасно. Странно, но все-таки доказал. Итог: ускорение в 10 раз.

>Юрий Зотов ©   (10.04.17 15:08) [157]
>Это азбука, и она правильная. А на практике было вот что:

Ну да, это реалии жизни. Поэтому если нет полного контроля над базой, то только периодический тест на ее адекватность. Из недавних примеров: есть база, из нее строится куча отчетов. В основном после ее ежемесячного пополнения. Данные поступают корявые, их правят, но косяки в базу просачиваются. В час Х начинаются строится отчеты и валятся через один. Ищут, исправляют и дальше. Была сделана система тестов для ПРЕДВАРИТЕЛЬНОЙ проверки. В результате все косяковое находится гарантированно и автоматом, правится и вперед с песней к отчетам! Время получения оных сократилось в несколько раз, сложность и нервность процесса вообще испарились.

Сергей Суровцев ©   (10.04.17 15:39) [158]


> Данные поступают корявые, их правят, но косяки в базу просачиваются


Что это у вас за база такая ? Мне право интересно.

> Юрий Зотов ©   (10.04.17 15:08) [157]


> А на практике было вот что:
> - триггеры запрещены;
> - хранимки запрещены;
> - внешние ключи запрещены (они, конечно, есть, но БД об
> этом не знает);
> - нормализация данных близка к нулю;
> - и т.п.

Юр, мне кажется, что я знаю, что это за проект :о))

> pavel_guzhanov ©   (10.04.17 16:28) [160]

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

А вот тот проект, которого ты изнутри не знаешь (ну, ты понял, да?) - это достойный экспонат для выставки. Претендент на медаль.

Юрий Зотов ©   (10.04.17 16:41) [161]

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

Я могу представить причины почему триггеры и хранимки запрещены, но внешние ключи-то за что?

> Но даже если что-то сделано криво, я не до конца понимаю,
>  зачем эту кривизну приводить в пример ?

Игорь, это не "сделано криво", это требования заказчика

> Игорь Шевченко ©   (10.04.17 16:50) [162]

> зачем эту кривизну приводить в пример ?

А что еще приводить в пример кривизны, как не кривизну?

> Kerk ©   (10.04.17 16:51) [163]

> внешние ключи-то за что?

Уже несколько лет тоже не могу этого понять. Заказчик так хочет, а его пути неисповедимы.

pavel_guzhanov ©   (10.04.17 16:52) [164]
Юрий Зотов ©   (10.04.17 17:09) [165]


> Игорь, это не "сделано криво", это требования заказчика


Не понял. Заказчик вроде занимается своей прикладной областью, в которой такие понятия, как внешние ключи отсутствуют.

> Игорь Шевченко ©   (10.04.17 17:13) [166]

некоторые заказчики очень "умные".

> Игорь Шевченко ©   (10.04.17 17:13) [166]

У заказчика есть свои айтишники, причем грамотные. Какую-то часть они пишут сами, какую-то отдают подрядчику. Наверное, людей маловато.

Юрий Зотов ©   (10.04.17 17:22) [168]

Могу только посочувствовать. Но я бы не стал приводить в пример такие конструкции.

>Игорь Шевченко ©   (10.04.17 16:08) [159]
>Что это у вас за база такая ? Мне право интересно.

В двух словах: по всей стране куча народу вбивает данные с еще большей кучи бланков, заполняемых вручную. Информация искажается и на этапе заполнения, и на этапе набивания. Часть параметров не обязательна к заполнению, но обязательна на этапе обработки и проставляется из справочников, которые тоже не всегда дают однозначное соответствие - много родственных и малоотличающихся параметров, зависящих от многих деталей и факторов. Плюс к этому взаимозависимая информация поступает и обрабатывается частями, но в итоге должна составлять целостную картину. Примерно так.

>но внешние ключи-то за что?

например, погоня за производительностью. Как ни крути - любая проверка это время. И я знаю, что на поле скорее всего будет наложен индекс, но тем не менее.
А особенно если удаляется запись из таблицы,на которую могут ссылаться множество других таблиц - тогда надо проверить кто из допустим сотни таблиц может ссылаться на удаляемую запись.

Например, CBOSS на оракле не использовал внешние ключи, по крайней мере во времена когда биллинг мтс сидел на них.

>Игорь Шевченко ©   (10.04.17 17:26) [169]
>Могу только посочувствовать. Но я бы не стал приводить в пример такие конструкции.

Эти конструкции чрезвычайно распространены. Где-то лучше, где-то хуже, но в целом рядовое явление. Даже можно сказать естественное, системы создавались десятилетиями, разными разработчиками, при разных руководителях с разными приоритетами, идеями фикс, страхами и причудами. И вот в это приходится встраивать что-то свое.
Единственный способ не сталкиваться с этим - создавать готовый базовый программный комплекс для решения каких-то серьезных задач. Тогда уже поставщик ПО диктует условия, а заказчик либо принимает их, либо не берет это ПО. Компромиссы, конечно, возможны, но по мелочам, не затрагивая основной функционал.

В качестве примера могу привести работу, которой удалось избежать. Была у одного заказчика идея оплачивать работу сотрудников по минутам. На проходной стоял аппарат и по пальцу фиксировал кто когда пришел, выходил и заходил в течении дня, когда ушел. Эта идея не нравилась никому кроме директора. Кроме того интерфейс у системы - текстовый файл, причем крайне корявый.
Отговорить его смогли только показав, что по данным системы человек может 3 раза войти и только 1 раз выйти, или наоборот, или вообще не входить, зато 2 раза выходить и т.д. Месяц они пытались наладить пару вход-выход, но так и не смогли.

Сергей Суровцев ©   (11.04.17 00:05) [172]

Мне очень жаль, что тебе приходилось/приходится сталкиваться с подобным негативом. Но поверь, положительных примеров на порядок, а то и несколько, больше.

>Игорь Шевченко ©   (11.04.17 10:15) [174]
>Но поверь, положительных примеров на порядок, а то и несколько, больше.

Игорь, если можно, приведи несколько примеров. Не в плане доказательства, а для поднятия настроения. )))

Сергей Суровцев ©   (11.04.17 10:50) [175]

Несколько примеров чего ??? Я, например, занимаюсь базами данных, довольно давно, больше 30 лет, не одну систему написал сотоварищи, ни разу с подобными (а давайте мы базу как свалку использовать будем) заявлениями/пожеланиями не сталкивался.

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

>Игорь Шевченко ©   (11.04.17 10:59) [176]

Так об этом и речь. Когда ты сам делаешь базу, с нуля, то все кульно и рульно. А уж если еще и ввод в нее контролируешь, вообще идеал.
А вот когда тебе говорят - У нас есть база! Она ведется чуть ли не от князя Владимира, в ней есть ВСЯ необходимая информация, нужно только пристроить к ней набор отчетов!
А ты смотришь на эту базу и видишь, что инфа в нее вносилась в разное время по разным правилам, что-то они придумали значительно позже и эта инфа есть только за последнее время, а раньше ее в принципе нет, там где должны бы быть справочники - голое поле, про индексы никто и не слышал и т.д. Но они-то уверенны, у них все замечательно! И когда говоришь им о сроках и стоимости в таких условиях, на тебя смотрят как на марсианина - там же делать нечего! А от предложения перестроить их базу у них начинается нервный тик и неадекватные реакции, потому что страшно трогать, кто отвечать потом будет?

Сергей Суровцев ©   (11.04.17 11:35) [177]

Еще раз - я занимаюсь разработкой систем. Мне кажется, что не я один. На форумах и в реальной жизни я общаюсь с коллегами и могу примерно судить о качестве других проектов.

И да, наколенная кустарщина меня не интересует.

>Игорь Шевченко ©   (11.04.17 12:10) [178]
>Еще раз - я занимаюсь разработкой систем. Мне кажется, что не я один.

Да кто с тобой спорит, что нормально разработанные системы - это хорошо? Или о том что их много?

>И да, наколенная кустарщина меня не интересует.

Поверь на слово, тем, кому с ней приходится сталкиваться она тоже радости не приносит.

Сергей Суровцев ©   (11.04.17 12:33) [179]

Охотно верю, но это, скорее, родимые пятна тех лет, когда расхватывали любую автоматизацию, лишь бы как-то крутилось :)

самые лучшие бд создаю я. потому что:
а) вся бд в одной табличке
б) все поля типа var
в) никакого геморроя с индексами, триггерами, процедурами - их нет.

> самые лучшие бд создаю я. потому что:
так все-таки, они в одном файле или больше? )

в одном конечно. иначе не были бы такими самыми лучшими

Давно не заходил на форум. Смотрю, интерестная темка, но уже столько понаписывали....

ИМХО оба числа перед сравнением преобразуем так:




т.е. диапазон нечетных чисел преобразовываем в диапазон положительных чисел не меняя порядка их следования, а диапазон четных чисел преобразовываем в диапазон отрицательных чисел, меняя при этом порядок их сделования на противоположный.

А. ну да... По сути это та же идея, что описана в ссылке, приведенной в [2]