प्राकृतिक जावास्क्रिप्ट स्ट्रिंग छँटाई

क्रमबद्ध करने की समस्या शायद प्रोग्रामर द्वारा सबसे अधिक हल की जाने वाली समस्या है। इस तथ्य के बावजूद कि इतने व्यापक एल्गोरिदम नहीं हैं और उन सभी को लंबे समय से किसी भी भाषा और प्लेटफार्मों के लिए लिखा और अनुकूलित किया गया है, सॉर्टलिस्ट () और स्रोत कोड में समान तरीके फ्लैश होते हैं। शायद, हम में से प्रत्येक ने एक से अधिक बार छंटाई के बुलबुले लिखे और सोचा कि यह पहली बार काम क्यों नहीं करता है।

हालाँकि, यह छँटाई एल्गोरिथ्म के बारे में नहीं है, बल्कि एक स्ट्रिंग तुलना विधि के बारे में है। ऐसा लगता है कि यहां सब कुछ तुच्छ है - बस शुरुआत से पहले विभिन्न पात्रों की तुलना करें। और अगर लाइनों में नंबर हैं? फिर यह सॉर्टिंग ( lexicographic ) अनुक्रम ['file2', 'file10', 'file1'] को ['file1', 'file10', 'file2'] में रूपांतरित करता है। लेकिन एक व्यक्ति पाठ पढ़ते समय संख्याओं को मानता है, और उसी क्रम, सहज रूप से आदेश दिया गया, इस तरह दिखता है: ['file1', 'file2', 'file10']। इस तरह की छँटाई को प्राकृतिक छँटाई कहा जाता है।

कटौती के तहत - बाइक के लिए एक विस्तृत जावास्क्रिप्ट एल्गोरिदम। यह इष्टतमता और सुंदरता का ढोंग नहीं करता है, लेकिन फिर भी एक बहु-पास कार्यान्वयन "हेड-ऑन" से बेहतर है।



हम स्वयं छँटाई एल्गोरिथ्म नहीं लिखेंगे, लेकिन अंतर्निहित Array.sort () पद्धति का उपयोग करेंगे। इसलिए, "मुख्य कार्य" कुछ इस तरह दिखाई देगा:

function naturalSort(stringArray) {
var arr = stringArray;
// ...
return arr.sort(compareStrings) //
}

यह स्ट्रिंग्स की तुलना करने के लिए फंक्शनस्ट्रीम () फ़ंक्शन लिखने के लिए रहता है। यह अलग-अलग तरीकों से किया जा सकता है, लेकिन निम्नलिखित दृष्टिकोण मेरे लिए हुआ: हम लाइनों में पाठ से संख्याओं को अलग करते हैं, और फिर परिणामी सरणियों के माध्यम से एक ही सूचकांक के साथ लाइनों (या संख्याओं) के बीच पहले अंतर पर जाते हैं। स्प्लिटस्ट्रिंग () फ़ंक्शन (इसके बारे में थोड़ी देर बाद) लाइनों को अलग कर देगा, और तुलना स्वयं कुछ इस तरह दिखाई देगी:

function compareStrings(str1, str2) {
//
var compare = function (a, b) {
return (a < b) ? -1 : (a > b) ? 1 : 0;
};
// ; splitString()
var parts1 = splitString(str1);
var parts2 = splitString(str2);
//
var minLength = Math.min(parts1.length, parts2.length);
for ( var i = 0; i < minLength; i++) {
//
}
//
// , "", , ""
return compare(parts1.length, parts2.length);
}

हालांकि, इस दृष्टिकोण के साथ सब कुछ इतना आसान नहीं है: अधिकांश रेखाएं जिनकी तुलना पहले वर्णों से भिन्न होती है, यानी स्प्लिटस्ट्रिंग () बहुत सारे अनावश्यक काम करती है। लेकिन यह आस्थगित गणनाओं का उपयोग करने के लिए ठीक है - स्प्लिटस्ट्रिंग () एक तैयार किए गए सरणी को वापस न करें, लेकिन अगले () और गणना () विधियों के साथ एक पुनरावृत्ति वस्तु। जावास्क्रिप्ट में बंद होने के लिए धन्यवाद, कार्यान्वयन बहुत अधिक नहीं था:
(पोस्ट के अंत में यूपीडी )

function splitString(str) {
var from = 0; // slice()
var index = 0; //
var count = 0; //
var splitter = {}; //
//
splitter.count = function () {
return count;
}
//
splitter.next = function () {
// - null
if (index === str.length) {
return null ;
}
//
while (++index) {
var currentIsDigit = isDigit(str.charAt(index - 1)); // isDigit()
var nextChar = str.charAt(index);
var currentIsLast = (index === str.length);
// - ,
// ( / )
var isBorder = currentIsLast ||
xor(currentIsDigit, isDigit(nextChar)); // xor()
if (isBorder) {
var part = str.slice(from, index);
from = index;
count++;
return {
IsNumber: currentIsDigit,
Value: currentIsDigit ? Number(part) : part
};
} // end if
} // end while
}; // end next()

return splitter;
}

हम सहायक कार्य लिखेंगे - xor () और isDigit ():

function xor(a, b) {
return a ? !b : b;
}

function isDigit(chr) {
var charCode = function (ch) {
return ch.charCodeAt(0);
};
var code = charCode(chr);
return (code >= charCode( '0' )) && (code <= charCode( '9' ));
}

अब वापस स्ट्रिंग तुलना फ़ंक्शन तुलना () के लिए करें। पुनरावृत्तियों की शुरुआत के साथ, सामान्य तर्क बहुत बदल नहीं गया है:
(पोस्ट के अंत में यूपीडी )

function compareStrings(str1, str2) {
//
var compare = function (a, b) {
return (a < b) ? -1 : (a > b) ? 1 : 0;
};
//
var splitter1 = splitString(str1);
var splitter2 = splitString(str2);
//
while ( true ) {
var first = splitter1.next();
var second = splitter2.next();
// ...
if ( null !== first && null !== second) {
// ( )
if (xor(first.IsNumber, second.IsNumber)) {
// ""
return first.IsNumber ? -1 : 1;
//
} else {
var comp = compare(first.Value, second.Value);
if (comp != 0) {
return comp;
}
} // end if
// ... - ""
} else {
return compare(splitter1.count(), splitter2.count());
}
} // end while
}

अंत में, हम छँटाई फ़ंक्शन लिखते हैं, इसे सभी को एक साथ रखते हैं और कोड को "कंघी" करते हैं:
(पोस्ट के अंत में यूपीडी )

function naturalSort(stringArray) {
// ""
var xor = function (a, b) {
return a ? !b : b;
};
// ,
var isDigit = function (chr) {
var charCode = function (ch) {
return ch.charCodeAt(0);
};
var code = charCode(chr);
return (code >= charCode( '0' )) && (code <= charCode( '9' ));
};
//
var splitString = function (str) {
var from = 0; // slice()
var index = 0; //
var count = 0; //
var splitter = {}; //
//
splitter.count = function () {
return count;
}
//
splitter.next = function () {
// - null
if (index === str.length) {
return null ;
}
//
while (++index) {
var currentIsDigit = isDigit(str.charAt(index - 1));
var nextChar = str.charAt(index);
var currentIsLast = (index === str.length);
// - ,
// ( / )
var isBorder = currentIsLast ||
xor(currentIsDigit, isDigit(nextChar));
if (isBorder) {
var part = str.slice(from, index);
from = index;
count++;
return {
IsNumber: currentIsDigit,
Value: currentIsDigit ? Number(part) : part
};
} // end if
} // end while
}; // end next()
return splitter;
};
// ""
var compareStrings = function (str1, str2) {
//
var compare = function (a, b) {
return (a < b) ? -1 : (a > b) ? 1 : 0;
};
//
var splitter1 = splitString(str1);
var splitter2 = splitString(str2);
//
while ( true ) {
var first = splitter1.next();
var second = splitter2.next();
// ...
if ( null !== first && null !== second) {
// ( )
if (xor(first.IsNumber, second.IsNumber)) {
// ""
return first.IsNumber ? -1 : 1;
//
} else {
var comp = compare(first.Value, second.Value);
if (comp != 0) {
return comp;
}
} // end if
// ... - ""
} else {
return compare(splitter1.count(), splitter2.count());
}
} // end while
}
//
var arr = stringArray;
return arr.sort(compareStrings);
}

मैं कोड के लिए बग, टिप्स और सुझावों के लिए आभारी रहूंगा। मुझे आशा है कि किसी को दिलचस्पी थी, और शायद उपयोगी भी।

युपीडी:
टिप्पणियों में, Alex_At_Net ने नोट किया कि लाइन ब्रेक के परिणामों को कैश करना अच्छा होगा, और स्टैंडी ने तुरंत लाइनों को टुकड़ों में तोड़ने और टुकड़ों के तैयार किए गए सेटों को छांटने का सुझाव दिया। परिणामस्वरूप, स्क्रिप्ट का एक संशोधित और संवर्धित संस्करण दिखाई दिया। एक वैकल्पिक चिमटा पैरामीटर को सॉर्टिंग फ़ंक्शन में जोड़ा गया है - एक मनमाना ऑब्जेक्ट को स्ट्रिंग में परिवर्तित करने का कार्य: अब आप किसी भी ऑब्जेक्ट के सरणियों को सॉर्ट कर सकते हैं। इनपुट ऐरे को तुरंत स्प्लिटर्स के एक सरणी में बदल दिया जाता है, लेकिन बंटवारा केवल तब होता है जब सूचकांक द्वारा टुकड़े को एक्सेस करना, केवल सही जगह पर और केवल एक बार। अगली () विधि के बजाय, फाड़नेवाला के पास अब एक भाग (i) विधि है जो सूचकांक द्वारा एक टुकड़ा लौटाता है। कोड थोड़ा और "कंघी" और "ऑब्जेक्टिफाइड" है। यह सब इस तरह दिखता है:

function naturalSort(array, extractor) {
"use strict" ;
//
var splitters = array.map(makeSplitter);
//
var sorted = splitters.sort(compareSplitters);
//
return sorted.map( function (splitter) {
return splitter.item;
});
//
function makeSplitter(item) {
return new Splitter(item);
}
//
// ""
function Splitter(item) {
var index = 0; //
var from = 0; //
var parts = []; //
var completed = false ; //
//
this .item = item;
// -
var key = ( typeof (extractor) === 'function' ) ?
extractor(item) :
item;
this .key = key;
//
this .count = function () {
return parts.length;
};
// ( parts[])
this .part = function (i) {
while (parts.length <= i && !completed) {
next(); //
}
return (i < parts.length) ? parts[i] : null ;
};
//
function next() {
//
if (index < key.length) {
//
while (++index) {
var currentIsDigit = isDigit(key.charAt(index - 1));
var nextChar = key.charAt(index);
var currentIsLast = (index === key.length);
// - ,
// ( / )
var isBorder = currentIsLast ||
xor(currentIsDigit, isDigit(nextChar));
if (isBorder) {
// parts[]
var partStr = key.slice(from, index);
parts.push( new Part(partStr, currentIsDigit));
from = index;
break ;
} // end if
} // end while
//
} else {
completed = true ;
} // end if
} // end next
//
function Part(text, isNumber) {
this .isNumber = isNumber;
this .value = isNumber ? Number(text) : text;
}
}
//
function compareSplitters(sp1, sp2) {
var i = 0;
do {
var first = sp1.part(i);
var second = sp2.part(i);
// ...
if ( null !== first && null !== second) {
// ( )
if (xor(first.isNumber, second.isNumber)) {
// ""
return first.isNumber ? -1 : 1;
//
} else {
var comp = compare(first.value, second.value);
if (comp != 0) {
return comp;
}
} // end if
// ... - ""
} else {
return compare(sp1.count(), sp2.count());
}
} while (++i);
//
function compare(a, b) {
return (a < b) ? -1 : (a > b) ? 1 : 0;
};
};
// ""
function xor(a, b) {
return a ? !b : b;
};
// :
function isDigit(chr) {
var code = charCode(chr);
return (code >= charCode( '0' )) && (code <= charCode( '9' ));
function charCode(ch) {
return ch.charCodeAt(0);
};
};
}

टिप्पणियों के साथ
कोई टिप्पणी नहीं

पुनश्च:

function thanks() {
alert( 'C PoiSoN Source Code Highlighter' );
};

* This source code was highlighted with Source Code Highlighter .