digitalmars.D.learn - Efficient sort function allowing own test and swap function as
- Alaindevos (6/6) Oct 06 2020 I have a large table consisting of two columns.One with
- H. S. Teoh (6/12) Oct 06 2020 Why don't you use std.algorithm.sort? That's what the standard library
- =?UTF-8?Q?Ali_=c3=87ehreli?= (109/116) Oct 06 2020 I had fun writing the following program. Note how makeIndex allows
- Imperatorn (2/8) Oct 07 2020 Nice use of iota!
- WebFreak001 (14/20) Oct 07 2020 you can use std.range:zip with std.algorithm:sort:
- Alaindevos (3/24) Oct 08 2020 This was what I was looking for. This zip combined with sort is
I have a large table consisting of two columns.One with words.Another with frequencies. I want to sort them efficiently according to the names or frequency. For this I need an efficient sort function where I can plugin my proper test of order, and proper swap. Currently I do it using an own written bubble sort that doesn't scale well.
Oct 06 2020
On Tue, Oct 06, 2020 at 10:18:39PM +0000, Alaindevos via Digitalmars-d-learn wrote:I have a large table consisting of two columns.One with words.Another with frequencies. I want to sort them efficiently according to the names or frequency. For this I need an efficient sort function where I can plugin my proper test of order, and proper swap. Currently I do it using an own written bubble sort that doesn't scale well.Why don't you use std.algorithm.sort? That's what the standard library is for. T -- Being able to learn is a great learning; being able to unlearn is a greater learning.
Oct 06 2020
On 10/6/20 3:18 PM, Alaindevos wrote:I have a large table consisting of two columns.One with words.Another with frequencies. I want to sort them efficiently according to the names or frequency. For this I need an efficient sort function where I can plugin my proper test of order, and proper swap. Currently I do it using an own written bubble sort that doesn't scale well.I had fun writing the following program. Note how makeIndex allows visiting elements in sorted order without actually sorting them. import std.random; import std.range; import std.algorithm; import std.conv; import std.stdio; struct S { string word; size_t frequency; } bool byWord(S a, S b) { return a.word < b.word; } bool byFrequency(S a, S b) { return a.frequency < b.frequency; } auto dump(R)(string title, R range) { writefln!"\n%s:\n%(%s\n%)"(title, range); } // A test function that makes an S S makeS() { string makeWord() { static letters = iota('a', 'z' + 1).map!(to!dchar).array; return letters.randomSample(4).to!string; // Four-letter words! :p } size_t makeFrequency() { return uniform(0, 100); } return S(makeWord(), makeFrequency()); } // A test function that makes some S'es S[] makeSs() { return 10.iota.map!(i => makeS()).array; } void main() { auto ss = makeSs(); dump("Unsorted", ss); auto byWordIndexes = new size_t[ss.length]; ss.makeIndex!byWord(byWordIndexes); dump("Still unsorted but visited by word order", byWordIndexes.map!(i => ss[i])); auto byFrequencyIndexes = new size_t[ss.length]; ss.makeIndex!byFrequency(byFrequencyIndexes); dump("Still unsorted but visited by frequency order", byFrequencyIndexes.map!(i => ss[i])); ss.sort!byWord(); dump("Actually sorted by words", ss); ss.sort!byFrequency(); dump("Actually sorted by frequencies", ss); } Sample output: Unsorted: S("bfmp", 78) S("imsx", 17) S("kmwy", 60) S("klpw", 92) S("hnrt", 24) S("aivz", 29) S("prst", 24) S("cdlm", 86) S("alvz", 13) S("mnxz", 52) Still unsorted but visited by word order: S("aivz", 29) S("alvz", 13) S("bfmp", 78) S("cdlm", 86) S("hnrt", 24) S("imsx", 17) S("klpw", 92) S("kmwy", 60) S("mnxz", 52) S("prst", 24) Still unsorted but visited by frequency order: S("alvz", 13) S("imsx", 17) S("hnrt", 24) S("prst", 24) S("aivz", 29) S("mnxz", 52) S("kmwy", 60) S("bfmp", 78) S("cdlm", 86) S("klpw", 92) Actually sorted by words: S("aivz", 29) S("alvz", 13) S("bfmp", 78) S("cdlm", 86) S("hnrt", 24) S("imsx", 17) S("klpw", 92) S("kmwy", 60) S("mnxz", 52) S("prst", 24) Actually sorted by frequencies: S("alvz", 13) S("imsx", 17) S("hnrt", 24) S("prst", 24) S("aivz", 29) S("mnxz", 52) S("kmwy", 60) S("bfmp", 78) S("cdlm", 86) S("klpw", 92) Ali
Oct 06 2020
On Wednesday, 7 October 2020 at 00:08:06 UTC, Ali Çehreli wrote:On 10/6/20 3:18 PM, Alaindevos wrote:Nice use of iota![...]I had fun writing the following program. Note how makeIndex allows visiting elements in sorted order without actually sorting them. [...]
Oct 07 2020
On Tuesday, 6 October 2020 at 22:18:39 UTC, Alaindevos wrote:I have a large table consisting of two columns.One with words.Another with frequencies. I want to sort them efficiently according to the names or frequency. For this I need an efficient sort function where I can plugin my proper test of order, and proper swap. Currently I do it using an own written bubble sort that doesn't scale well.you can use std.range:zip with std.algorithm:sort: import std; void main() { string[] names = ["Bob", "Alice", "Foo", "Bar"]; int[] freq = [5, 7, 1, 6]; zip(names, freq).sort!"a[0] < b[0]"; // sort by name writeln(names); writeln(freq); zip(names, freq).sort!"a[1] < b[1]"; // sort by frequency writeln(names); writeln(freq); }
Oct 07 2020
On Wednesday, 7 October 2020 at 11:05:39 UTC, WebFreak001 wrote:On Tuesday, 6 October 2020 at 22:18:39 UTC, Alaindevos wrote:This was what I was looking for. This zip combined with sort is powerful.I have a large table consisting of two columns.One with words.Another with frequencies. I want to sort them efficiently according to the names or frequency. For this I need an efficient sort function where I can plugin my proper test of order, and proper swap. Currently I do it using an own written bubble sort that doesn't scale well.you can use std.range:zip with std.algorithm:sort: import std; void main() { string[] names = ["Bob", "Alice", "Foo", "Bar"]; int[] freq = [5, 7, 1, 6]; zip(names, freq).sort!"a[0] < b[0]"; // sort by name writeln(names); writeln(freq); zip(names, freq).sort!"a[1] < b[1]"; // sort by frequency writeln(names); writeln(freq); }
Oct 08 2020