Javascript Radix Sırala

Question

Bir süredir internette dolaşıyordum ve genel olarak kullanılan Radix Sort'ın 'kararlı' bir defacto uygulaması olup olmadığını merak ediyorum.

İki tür yarıçap türü, en az anlamlı basamak (LSD) yarıçapı türleri ve en önemli basamak (MSD) yarıçapı türleridir.

LSD veya MSD'ye bir örnek arıyorum.

Answer 1

Benim versiyon daha ayrıntılı olduğunu, ancak bu bile öğelerin çok sayıda hızla yürütür:

 var testArray = [ 331, 454, 230, 34, 343, 45, 59, 453, 345, 231, 9 ]; 

    function radixBucketSort (arr) { 
    var idx1, idx2, idx3, len1, len2, radix, radixKey; 
    var radices = {}, buckets = {}, num, curr; 
    var currLen, radixStr, currBucket; 

    len1 = arr.length; 
    len2 = 10; // radix sort uses ten buckets 

    // find the relevant radices to process for efficiency   
    for (idx1 = 0;idx1 < len1;idx1++) { 
     radices[arr[idx1].toString().length] = 0; 
    } 

    // loop for each radix. For each radix we put all the items 
    // in buckets, and then pull them out of the buckets. 
    for (radix in radices) {   
     // put each array item in a bucket based on its radix value 
     len1 = arr.length; 
     for (idx1 = 0;idx1 < len1;idx1++) { 
     curr = arr[idx1]; 
     // item length is used to find its current radix value 
     currLen = curr.toString().length; 
     // only put the item in a radix bucket if the item 
     // key is as long as the radix 
     if (currLen >= radix) { 
      // radix starts from beginning of key, so need to 
      // adjust to get redix values from start of stringified key 
      radixKey = curr.toString()[currLen - radix]; 
      // create the bucket if it does not already exist 
      if (!buckets.hasOwnProperty(radixKey)) { 
      buckets[radixKey] = []; 
      } 
      // put the array value in the bucket 
      buckets[radixKey].push(curr);   
     } else { 
      if (!buckets.hasOwnProperty('0')) { 
      buckets['0'] = []; 
      } 
      buckets['0'].push(curr);   
     } 
     } 
     // for current radix, items are in buckets, now put them 
     // back in the array based on their buckets 
     // this index moves us through the array as we insert items 
     idx1 = 0; 
     // go through all the buckets 
     for (idx2 = 0;idx2 < len2;idx2++) { 
     // only process buckets with items 
     if (buckets[idx2] != null) { 
      currBucket = buckets[idx2]; 
      // insert all bucket items into array 
      len1 = currBucket.length; 
      for (idx3 = 0;idx3 < len1;idx3++) { 
      arr[idx1++] = currBucket[idx3]; 
      } 
     } 
     } 
     buckets = {}; 
    } 
    } 
    radixBucketSort(testArray); 
    console.dir(testArray);   

Answer 2

JavaScript LSD sıralama:

var counter = [[]]; 
function sortLSD(array, maxDigitSymbols) { 
    var mod = 10; 
    var dev = 1; 
    for (var i = 0; i < maxDigitSymbols; i++, dev *= 10, mod *= 10) { 
     for (var j = 0; j < array.length; j++) { 
      var bucket = parseInt((array[j] % mod)/dev); 
      if (counter[bucket] == null) { 
       counter[bucket] = []; 
      } 
      counter[bucket].push(array[j]); 
     } 
     var pos = 0; 
     for (var j = 0; j < counter.length; j++) { 
      var value = null ; 
      if (counter[j] != null) { 
       while ((value = counter[j].shift()) != null) { 
        array[pos++] = value; 
       } 
      } 
     } 
    } 
    return array; 
} 
var test = [22, 1,2,9,3,2,5,14,66]; 
console.log(sortLSD(test, 2)); 

Answer 3

aşağıdaki kodu ile öğeleri çok sayıda dizi geçebilir .

var counter = [[]]; // Radix sort Array container to hold arrays from 0th digit to 9th digits 
 
    function radixSortLSD(array) { 
 
     var max = 0, mod = 10,dev = 1; //max 
 
     for(var i=0;i<array.length;i++){ 
 
      if(array[i] >max){ 
 
       max = array[i]; 
 
      } 
 
     } 
 
     // determine the large item length 
 
     var maxDigitLength = (max+'').length; 
 
     for (var i = 0; i < maxDigitLength; i++, dev *= 10, mod *= 10) { 
 
      for(var j = 0; j < array.length; j++) { 
 
       var bucket = Math.floor((array[j] % mod)/dev);// Formula to get the significant digit 
 
       if(counter[bucket]==undefined) { 
 
        counter[bucket] = []; 
 
       } 
 
       counter[bucket].push(array[j]); 
 
      } 
 
      var pos = 0; 
 
      for(var j = 0; j < counter.length; j++) { 
 
       var value = undefined; 
 
       if(counter[j]!=undefined) { 
 
        while ((value = counter[j].shift()) != undefined) { 
 
         array[pos++] = value; 
 
        } 
 
       } 
 
      } 
 
     } 
 
     console.log("ARRAY: "+array); 
 
    }; 
 
var sampleArray = [1,121,99553435535353534,345,0]; 
 
radixSortLSD(sampleArray);

Answer 4

Radix Sıralama harika lineer zamanda sıralama algoritmasıdır. CPU ve GPU için birçok hızlı uygulama yapılmıştır. İşte benim C++ uygulamasından JavaScript'e çevrilmiş bir tane. Ben kitap radix tür gizli kökenlerini sağlanan CRLs 3rd edition bölüm 8.3

yılında radix tür karşılaştı işaretsiz tamsayılar High Performance Radix Sort LSD

Answer 5

sıralarını sıralamak için 5 50X daha hızlı JavaScript yerleşik tür karşılaştırır ve olduğunu. MSD sürümünü antika ve zor olarak tanımladı. Ayrıca LSD'nin uygulanmasını tavsiye etti.

Burada, bu tekniği kullanarak yarıçap sıralamasının uygulanmasını sağlarım. Sözde kod tarafından

başlayalım:

/** 
* @param k: the max of input, used to create a range for our buckets 
* @param exp: 1, 10, 100, 1000, ... used to calculate the nth digit 
*/ 
Array.prototype.countingSort = function (k, exp) { 
    /* eslint consistent-this:0 */ 
    /* self of course refers to this array */ 
    const self = this; 

    /** 
    * let's say the this[i] = 123, if exp is 100 returns 1, if exp 10 returns 2, if exp is 1 returns 3 
    * @param i 
    * @returns {*} 
    */ 
    function index(i) { 
     if (exp) 
      return Math.floor(self[i]/exp) % 10; 
     return i; 
    } 

    const LENGTH = this.length; 

    /* create an array of zeroes */ 
    let C = Array.apply(null, new Array(k)).map(() => 0); 
    let B = []; 

    for (let i = 0; i < LENGTH; i++) 
     C[index(i)]++; 

    for (let i = 1; i < k; i++) 
     C[i] += C[i - 1]; 

    for (let i = LENGTH - 1; i >= 0; i--) { 
     B[--C[index(i)]] = this[i]; 
    } 

    B.forEach((e, i) => { 
     self[i] = e 
    }); 
} 

Ve bu sadece zor kısmı, gerisi burada

Array.prototype.radixSort = function() { 
    const MAX = Math.max.apply(null, this); 

    /* let's say the max is 1926, we should only use exponents 1, 10, 100, 1000 */ 
    for (let exp = 1; MAX/exp > 1; exp *= 10) { 
     this.countingSort(10, exp); 
    } 
} 

Şimdi çok basit bir nasıl yapabilirsiniz olduğunu bu yöntemi test edin

let a = [589, 111, 777, 65, 124, 852, 345, 888, 553, 654, 549, 448, 222, 165]; 
a.radixSort() 
console.log(a); 

Son olarak, kitapta belirtildiği gibi, bu özel algoritma sadece sayma sıralaması yerinde bir sıralama algoritmasıdır, yani iki eleman birbirine bağlanırsa, girdi dizisinde onların oluşum sırası korunur.

Answer 6

Aşağıdaki işlev, Uint32 değerlerinde LSB yarıçapı sıralama yapar. Bu arada, yerleşik sıralama işlevinden daha hızlıdır.

O performansını artırmak için diziler daktilo, ancak sürece sadece 32 bitlik değerleri içeren olarak, düz diziler geçirirseniz tıpkı iyi çalışır kullanır:

function radixSortUint32(input) { 
    const arrayConstr = input.length < (1 << 16) ? 
    Uint16Array : 
    Uint32Array; 
    const numberOfBins = 256 * 4; 
    let count = new arrayConstr(numberOfBins); 

    let output = new Uint32Array(input.length); 

    // count all bytes in one pass 
    for (let i = 0; i < input.length; i++) { 
    let val = input[i]; 
    count[val & 0xFF]++; 
    count[((val >> 8) & 0xFF) + 256]++; 
    count[((val >> 16) & 0xFF) + 512]++; 
    count[((val >> 24) & 0xFF) + 768]++; 
    } 

    // create summed array 
    for (let j = 0; j < 4; j++) { 
    let t = 0, 
     sum = 0, 
     offset = j * 256; 
    for (let i = 0; i < 256; i++) { 
     t = count[i + offset]; 
     count[i + offset] = sum; 
     sum += t; 
    } 
    } 

    for (let i = 0; i < input.length; i++) { 
    let val = input[i]; 
    output[count[val & 0xFF]++] = val; 
    } 
    for (let i = 0; i < input.length; i++) { 
    let val = output[i]; 
    input[count[((val >> 8) & 0xFF) + 256]++] = val; 
    } 
    for (let i = 0; i < input.length; i++) { 
    let val = input[i]; 
    output[count[((val >> 16) & 0xFF) + 512]++] = val; 
    } 
    for (let i = 0; i < input.length; i++) { 
    let val = output[i]; 
    input[count[((val >> 24) & 0xFF) + 768]++] = val; 
    } 

    return input; 
} 

Burada Int32 için yukarıdaki yeniden kullanmak nasıl oluyor değerler:

function radixSortInt32(input) { 
    // make use of ArrayBuffer to "reinterpret cast" 
    // the Int32Array as a Uint32Array 
    let uinput = input.buffer ? 
    new Uint32Array(input.buffer): 
    Uint32Array.from(input); 

    // adjust to positive nrs 
    for (let i = 0; i < uinput.length; i++) { 
    uinput[i] += 0x80000000; 
    } 

    // re-use radixSortUint32 
    radixSortUint32(uinput); 

    // adjust back to signed nrs 
    for (let i = 0; i < uinput.length; i++) { 
    uinput[i] -= 0x80000000; 
    } 

    // for plain arrays, fake in-place behaviour 
    if (input.buffer === undefined){ 
    for (let i = 0; i < input.length; i++){ 
     input[i] = uinput[i]; 
    } 
    } 

    return input; 
} 

Ve Float32 değerleri için de benzer bir hile:

function radixSortFloat32(input) { 
    // make use of ArrayBuffer to "reinterpret cast" 
    // the Float32Array as a Uint32Array 
    let uinput = input.buffer ? 
    new Uint32Array(input.buffer) : 
    new Uint32Array(Float32Array.from(input).buffer); 

    // Similar to radixSortInt32, but uses a more complicated trick 
    // See: http://stereopsis.com/radixSort.html 
    for (let i = 0; i < uinput.length; i++) { 
    if (uinput[i] & 0x80000000) { 
     uinput[i] ^= 0xFFFFFFFF; 
    } else { 
     uinput[i] ^= 0x80000000; 
    } 
    } 

    // re-use radixSortUint32 
    radixSortUint32(uinput); 

    // adjust back to original floating point nrs 
    for (let i = 0; i < uinput.length; i++) { 
    if (uinput[i] & 0x80000000) { 
     uinput[i] ^= 0x80000000; 
    } else { 
     uinput[i] ^= 0xFFFFFFFF; 
    } 
    } 

    if (input.buffer === undefined){ 
    let floatTemp = new Float32Array(uinput.buffer); 
    for(let i = 0; i < input.length; i++){ 
     input[i] = floatTemp[i]; 
    } 
    } 

    return input; 
} 

32 bit veya daha az olan tüm TypedArrays ile çalışan bu işlevler kümesi yaptım. Yani:

• Uint32Array
• Int32Array
• Float32Array
• Uint16Array
• Int16Array
• Uint8Array
• Int8Array
• Eğer tüm değerleri bilmek Herhangi düz dizi bu kriterlerden biri uyacak

Full gist here. Daha sonra Float64'e gidebilirim, temelde tüm javascript numaraları için destek alabilirdik.

TypedArray benchmarks shows radix beats the built-in sort function.

It's faster with plain arrays too, although not quite as much because of the added overhead