Jump to content

    

Кризис в самообразовании.

Сортировка in-place:

 

#!/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)

 

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]

Этот вариант и работать должен быстрее. Хотя он не такой наглядный для неподготовленного человека.

Share this post


Link to post
Share on other sites
ПС понравилась функция сравнения у вас. Мне и в голову не пришло, что так можно.

Указатель на функцию-предикат можно также и на С++ использовать:

// 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

Edited by =SSN=

Share this post


Link to post
Share on other sites
Guest TSerg
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);

 

 

Share this post


Link to post
Share on other sites

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

 

1.0882549455855042

 

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

 

0.48738399290014056

 

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

 

P.S. Вариант с лямбдой работает только с натуральными числами. Если надо весь целый диапазон, то ключевую функцию надо поправить соответственно.

Share this post


Link to post
Share on other sites
Почему не на месте? В книге Шилдта есть такой код:

 

Спасибо, что поправили.

Какие-то у меня в голове странные ассоциации сложились по поводу "на месте" и "O(1) потребления памяти".

Share this post


Link to post
Share on other sites
А уж про синтаксические правила и говорить нечего. Ведь это же надо придумать конструкции вроде такой:

 

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

 

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

 

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

 

Берем идентификатор и вокруг него раскручиваем спиральку:

af /*af - идентификатор*/

[] /*значит, af - это массив*/

* /*значит, это массив указателей на...*/

(int) /* скобки - принадлежность функции, внутри скобок - ее параметры, значит массив указателей на функции принимающие в качестве параметра тип int */

int /* тип возращаемого результата вышеупомянутыми функциями, ...... */

Edited by aiwa

Share this post


Link to post
Share on other sites
Было сказано, чтобы читабельно и понимабельно бегиннерам - т.е. разумная декомпозиция. Но для любителей говнокода, извольте:

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:

 

Да нет, я не тролю. Тема мне не интересна, просто только что мне пришла ссылка с рекламой Node.js для embedded,

где довольно изящно опустили Python - http://embedded-computing.com/articles/spe...-using-node-js/

Share this post


Link to post
Share on other sites
Guest TSerg
.. до этого никогда Node.js в руках не держал.

Кто хорошо освоил один из ЯП, нет проблем перейти на другой.

Точнее, проблемы будут, но не с синтаксисом, а либами.

P.S.

Питон - это не панацея, но один из вариантов современных языковых технологий.

 

 

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

Есть конечно, фикус - массив остается прежним :)

 

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

Share this post


Link to post
Share on other sites
Нет, ну действительно у создателей питона не было целью сделать жизнь легче.

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

 

Вот пример на 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 в руках не держал.

Что тут ясно и понятно? Какое-то нагромождение "проприетарных" ключевых слов. При этом длинно и рыхло. Уже приводил выше, но повторю:

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

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

 

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

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

 

Share this post


Link to post
Share on other sites
Guest TSerg
.. вся фишка этих кратких и красивых вариантах на ЯВУ - в использовании библиотек.

Не только.

Есть такие понятия, как "синтаксический сахар" и "синтаксическая соль".

Применение первого, обеспечивает, по выражению Джек Криншоу:

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

Сам термин "syntactic sugar" был введен Peter J. Landin в 1964 г. для описания синтаксиса алголо-подобного языка с использованием лямбда-исчисления.

Пример во многих ЯВУ - дополнение базового безусловного цикла, сначала тремя циклами (пред-, пост-условие, цикл с шагом), а затем и foreach.

Или, к примеру (x := x + y) == (x+=y); Это стандартно для C, но для Pascal - нет. Тем не менее, отечественные разработчики PascalABC.Net, сознательно пошли на значительную переделку Object Pascal, для сближения его с современными технологиями.

 

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

Пример в Delphi - override.

Или, например - завершение операции точкой с запятой.

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

Share this post


Link to post
Share on other sites
Или, к примеру (x := x + y) == (x+=y); Это стандартно для C, но для Pascal - нет.

Это имеет конечный смысл, особенно на безаккумуляторных архитектурах.

Так же, как ++ и --

Share this post


Link to post
Share on other sites
Или, к примеру (x := x + y) == (x+=y); Это стандартно для C, но для Pascal - нет. Тем не менее, отечественные разработчики PascalABC.Net, сознательно пошли на значительную переделку Object Pascal, для сближения его с современными технологиями.

 

Просто таки замечательный пример тарабарщины на ровном месте, в большинстве современные языки превратились в совершенно нечитабельную вещь в себе, в отличие от старых книг с алгоритмами на фортране и паскале. ИМХО

Share this post


Link to post
Share on other sites
Guest TSerg
Просто таки замечательный пример тарабарщины на ровном месте, в большинстве современные языки превратились в совершенно нечитабельную вещь в себе, в отличие от старых книг с алгоритмами на фортране и паскале. ИМХО

BASIC - наше все, с нумерацией строк, GOSUB и полной свободой.

Share this post


Link to post
Share on other sites
Guest TSerg

Еще один, очень красивый и, практически, кросс-языковый вариант решения задачи сортировки четных-нечетных:

(хотя он подразумевает, что изначально числа заданы в положительном диапазоне)

 

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

Share this post


Link to post
Share on other sites
Еще один, очень красивый и, практически, кросс-языковый вариант решения задачи сортировки четных-нечетных:

(хотя он подразумевает, что изначально числа заданы в положительном диапазоне)

 

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 именно этот финт и использован. И тоже только для положительных целых. Для любых целых это трансформируется в

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this