Penyortiran patologis

Bos Anda menuntut Anda mengembangkan algoritma penyortiran untuk meningkatkan kinerja aplikasi perusahaan Anda. Namun, setelah menulis aplikasi, Anda tahu bahwa Anda tidak mungkin membuatnya lebih cepat secara signifikan. Tidak ingin mengecewakan bos Anda, Anda telah memutuskan untuk mengembangkan algoritma baru yang bekerja lebih baik daripada * mengurutkan pada set data tertentu. Tentu saja, Anda tidak dapat membuatnya jelas bahwa algoritme hanya berfungsi pada beberapa kasus, jadi Anda ingin membuatnya tidak jelas.

Tujuan dari kontes ini adalah untuk menulis rutin penyortiran dalam bahasa pilihan Anda yang berkinerja lebih baik pada set data tertentu daripada yang lain, dengan hasil yang berulang. Semakin spesifik klasifikasi yang menentukan kecepatan, semakin baik. Algoritme harus melakukan semacam penyortiran, sehingga suatu algoritma yang bergantung pada data yang sudah sepenuhnya diurutkan (seperti dalam, suatu algoritma yang tidak melakukan apa-apa), atau suatu algoritma yang tergantung pada data yang sepenuhnya diurutkan secara terbalik, keduanya tidak valid. Algoritma pengurutan harus dengan benar mengurutkan setiap set data.

Setelah mempresentasikan rutinitas Anda, harap sertakan penjelasan mengapa itu hanya bekerja pada set data tertentu, dan sertakan uji coba pada setidaknya satu set data baik (cepat) dan satu set data buruk (lambat). Intinya di sini adalah untuk dapat membuktikan kepada atasan Anda bahwa Anda telah menemukan cara yang lebih baik untuk menyortir, sehingga lebih banyak data uji lebih baik. Tentu saja, Anda hanya akan menunjukkan kepada bos Anda hasil tes dari data yang baik, sehingga kesalahan dalam data pengujian yang diperlukan tidak terlalu jelas. Jika berlaku untuk bahasa Anda, harap tunjukkan bahwa algoritme Anda lebih cepat daripada algoritme penyortiran bawaan bahasa Anda.

Sebagai contoh, seseorang dapat mengirimkan algoritma penyisipan, dengan data yang baik adalah data yang sudah hampir diurutkan, dan data yang buruk menjadi data yang benar-benar acak, karena pendekatan penyisipan mendekati O (n) pada data yang hampir diurutkan. Namun, ini tidak terlalu baik, karena bos saya mungkin akan memperhatikan bahwa semua data pengujian hampir diurutkan sejak awal.

Ini adalah kontes popularitas , jadi jawabannya dengan suara terbanyak setelah 7 hari (21 Mei) menang.

Jika tidak ada yang mengalahkan saya, saya ingin mengirimkan jawaban wiki komunitas yang memanfaatkan kumpulan data yang terdistribusi secara seragam.

Sudah cukup lama, tapi saya ingat kembali di Algoritma 101 kami diajarkan beberapa algoritma penyortiran yang menggunakan pengacakan. Saya bukan murid yang sangat baik sehingga saya tidak begitu ingat bagaimana hasilnya atau mengapa rata-rata bekerja dengan cepat.

Namun demikian, saya telah memutuskan bahwa masalah ini memerlukan solusi yang menggunakan pengacakan, yang diharapkan akan bekerja sesuai keinginan saya rata-rata.

import random

def arrayIsSorted (arr) :
    for i in range(len(arr)-1) :
        if arr[i]>arr[i+1] : return False
    return True

def rSort (arr) :
    random.seed (42)
    counter = 0
    while not arrayIsSorted(arr) :
        random.shuffle (arr)
        counter+=1
    print ("Sorted in %d iterations." % counter)
    return arr

Karena pengacakan yang benar itu penting, saya memastikan untuk menabur RNG dengan jawaban untuk Kehidupan, Semesta dan Segalanya. Setelah sedikit pengujian ternyata itu langkah yang cerdas! Lihat seberapa cepat 2 daftar yang sepenuhnya arbitrer ini diurutkan:

rSort ([6,1,4,2,3,7,5])
rSort ([8,9,6,1,4,7,2,3,5])

Keduanya disortir hanya dalam 1 iterasi - Anda tidak mungkin meminta fungsi yang lebih cepat dari itu!

Sekarang, harus diakui, beberapa daftar lain menghasilkan hasil yang sedikit lebih buruk ...

rSort ([5,1,4,2,3,7,6])
rSort ([8,9,6,1,4,7,2,5,3])

Ini disortir dalam iterasi 4.176 dan 94.523 masing-masing, yang sebenarnya membutuhkan waktu lebih dari satu detik ... tapi mari kita simpan fakta itu untuk diri kita sendiri agar tidak mengganggu siapa pun dari betapa menakjubkannya algoritma ini!

Edit:

Saya diminta membuktikan efisiensi algoritme saya pada daftar 100 item, jadi begini:

rSort ([70, 6, 52, 97, 85, 61, 62, 48, 30, 3, 11, 88, 39, 91, 98, 8, 54, 92, 44, 65, 69, 21, 58, 41, 60, 76, 27, 82, 93, 81, 20, 94, 22, 29, 49, 95, 40, 19, 55, 42, 43, 1, 0, 67, 35, 15, 51, 31, 16, 25, 5, 53, 37, 74, 86, 12, 13, 72, 56, 32, 47, 46, 59, 33, 80, 4, 45, 63, 57, 89, 7, 77, 14, 10, 34, 87, 18, 79, 9, 66, 24, 99, 64, 26, 78, 38, 90, 28, 83, 75, 68, 2, 17, 73, 96, 71, 23, 84, 36, 50])

Bahkan daftar panjang dan sepenuhnya sewenang-wenang ini akan diurutkan secara instan! Sungguh, saya harus menemukan algoritma penyortiran terbaik di dunia!

Jika Anda dapat membuat data Anda sendiri, maka itu cukup mudah - dapatkan data yang terlihat acak, tetapi sertakan kunci untuk penyortiran yang lebih cepat. Semua data lain menggunakan metode penyortiran asli, jadi rata - rata lebih baik.

Salah satu cara mudah adalah memastikan setiap item data memiliki kunci unik, dan kemudian hanya hash kunci. Ambil contoh daftar dengan angka 1-10.000, semuanya dikalikan 16, dan dengan angka acak 0-15 ditambahkan padanya (lihat fillArray () di bawah). Mereka akan terlihat acak, tetapi masing-masing memiliki kunci berurutan yang unik. Untuk menyortir, bagi dengan 16 (dalam C >> 4 sangat cepat) dan kemudian hanya menempatkan angka ke dalam array menggunakan kunci yang dihasilkan sebagai indeks. Satu lulus dan Anda selesai. Dalam pengujian, saya menemukan quicksort 30 kali lebih lambat dari sepuluh juta angka.

void fillArray(int *a,int len)
{
  for (int i=0;i<len;++i)
    a[i]=(i<<4)|(rand()&0xF);
  // shuffle later
}
void sortArray(int *a,int len)
{
  int key=0;
  int *r=new int[len];
  for (int i=0;i<len;++i)
  {
    key=a[i]>>4;
    r[key]=a[i];
  }
  memcpy(a,r,len*sizeof(int));
  delete[] r;
}
void shuffleArray(int *a,int len)
{
  int swap=0, k=0;
  for (int i=0;i<len;++i)
  {
    k=rand()%len;
    swap=a[k];
    a[k]=a[i];
    a[i]=swap;
  }
}
int qCompare(const void*a,const void*b)
{
  int result=*((int*)a)-*((int*)b);
  return result;
}
void main()
{
  int aLen=10000;
  int *a=new int[aLen];
  srand (time(NULL));
  fillArray(a,aLen);
  // time them
  long t0=0, d0=0, d1=0;
  // qsort
  shuffleArray(a,aLen);
  t0=::GetTickCount();
  qsort(a,aLen,sizeof(int),&qCompare);
  d0=::GetTickCount()-t0;
  // oursort
  shuffleArray(a,aLen);
  t0=::GetTickCount();
  sortArray(a,aLen);
  d1=::GetTickCount()-t0;
  delete[] a;
}

Apa pun yang memiliki kunci unik dapat diurutkan dengan cara ini - jika Anda memiliki memori untuk menyimpannya, tentu saja. Sebagai contoh, banyak database menggunakan id pelanggan numerik yang unik - jika daftarnya cukup kecil / berurutan ini dapat disimpan dalam memori. Atau cara lain untuk menerjemahkan rekaman ke nomor unik. Untuk info lebih lanjut, teliti Hash Macam, karena memang begitulah ...