www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - How to efficiently resolve Associative Arrays not being sorted?

reply BoQsc <vaidas.boqsc gmail.com> writes:
I want to read a file, put it into an array, make some search and 
replace on the content and output the modified text. However 
Associative Arrays seem to be unsorted by default. Should I drop 
the Associative Arrays and use something else? What are the ways 
to resolve this randomness in Associative Arrays?

ReadfileAndCopyContentIntoArray.d
 import std.stdio;
 
 int lineNumber = 0;
 char[][int] fileInArray;
 
 void main(){
 	File exampleFile = File("exampleText.txt");
 	foreach(line; exampleFile.byLine){
 		
 		lineNumber++;
 		fileInArray[lineNumber] ~= line;
 		
 	}
 	writeln(fileInArray);
 }
exampleText.txt
 The quick brown fox jumps over the lazy dog
 Sphinx of black quartz, judge my vow.
 How vexingly quick daft zebras jump!
 The five boxing wizards jump quickly
 Maecenas consectetur risus a lacus sodales iaculis.
 Morbi sed tortor sollicitudin, pharetra massa egestas, congue 
 massa.
 Sed sit amet nisi at ligula ultrices posuere quis nec est.
 Mauris vel purus viverra, pellentesque elit id, consequat felis.
The Command Prompt Output
 [6:"Morbi sed tortor sollicitudin, pharetra massa egestas, 
 congue massa.\r", 7:"Sed sit amet nisi at ligula ultrices pos
 uere quis nec est.\r", 2:"Sphinx of black quartz, judge my 
 vow.\r", 3:"How vexingly quick daft zebras jump!\r", 1:"The q
 uick brown fox jumps over the lazy dog\r", 8:"Mauris vel purus 
 viverra, pellentesque elit id, consequat felis.", 5:"Maec
 enas consectetur risus a lacus sodales iaculis.\r", 4:"The five 
 boxing wizards jump quickly\r"]
As can be seen in the Command Prompt Output, the array is not ordered correctly. It goes: 6: 7: 2: 3: 1: 8: 5: 4: Instead of 1: 2: 3: 4: 5: 6: 7: 8:
Jun 02 2020
next sibling parent Luis <luis.panadero gmail.com> writes:
On Tuesday, 2 June 2020 at 07:32:56 UTC, BoQsc wrote:
 I want to read a file, put it into an array, make some search 
 and replace on the content and output the modified text. 
 However Associative Arrays seem to be unsorted by default. 
 Should I drop the Associative Arrays and use something else? 
 What are the ways to resolve this randomness in Associative 
 Arrays?

 ReadfileAndCopyContentIntoArray.d
 import std.stdio;
 
 int lineNumber = 0;
 char[][int] fileInArray;
 
 void main(){
 	File exampleFile = File("exampleText.txt");
 	foreach(line; exampleFile.byLine){
 		
 		lineNumber++;
 		fileInArray[lineNumber] ~= line;
 		
 	}
 	writeln(fileInArray);
 }
exampleText.txt
 The quick brown fox jumps over the lazy dog
 Sphinx of black quartz, judge my vow.
 How vexingly quick daft zebras jump!
 The five boxing wizards jump quickly
 Maecenas consectetur risus a lacus sodales iaculis.
 Morbi sed tortor sollicitudin, pharetra massa egestas, congue 
 massa.
 Sed sit amet nisi at ligula ultrices posuere quis nec est.
 Mauris vel purus viverra, pellentesque elit id, consequat 
 felis.
The Command Prompt Output
 [6:"Morbi sed tortor sollicitudin, pharetra massa egestas, 
 congue massa.\r", 7:"Sed sit amet nisi at ligula ultrices pos
 uere quis nec est.\r", 2:"Sphinx of black quartz, judge my 
 vow.\r", 3:"How vexingly quick daft zebras jump!\r", 1:"The q
 uick brown fox jumps over the lazy dog\r", 8:"Mauris vel purus 
 viverra, pellentesque elit id, consequat felis.", 5:"Maec
 enas consectetur risus a lacus sodales iaculis.\r", 4:"The 
 five boxing wizards jump quickly\r"]
As can be seen in the Command Prompt Output, the array is not ordered correctly. It goes: 6: 7: 2: 3: 1: 8: 5: 4: Instead of 1: 2: 3: 4: 5: 6: 7: 8:
Associative arrays looks that uses internally a hash map. Hash maps are unordered. The ouput order, looks that is the result of where the hash algorithm it's inserting the key/value pair in the hashmap. If you need order, you need to use a TreeMap (D std lib, emsi_containers and containersd have TreeMap implementations) or something like Java LinkedHashMap if order by insertion it's enough.
Jun 02 2020
prev sibling next sibling parent =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 6/2/20 12:32 AM, BoQsc wrote:

 I want to read a file, put it into an array, make some search and
 replace on the content and output the modified text.
How large is the data? If it fits into memory, just read the whole thing, update it, sort the keys, and then output like this: import std.stdio; import std.algorithm; foreach (key; aa.keys.sort) { writeln(key, aa[key]); } Of course, you can save the sorted array in a local variable as well if you will use it again: auto keys = aa.keys.sort; One great thing about programs that read and write files is that unless the data is so large that it does not fit into physical memory, you can't feel the time cost of that sort operation. :) Ali
Jun 02 2020
prev sibling parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 6/2/20 3:32 AM, BoQsc wrote:
 I want to read a file, put it into an array, make some search and 
 replace on the content and output the modified text. However Associative 
 Arrays seem to be unsorted by default. Should I drop the Associative 
 Arrays and use something else? What are the ways to resolve this 
 randomness in Associative Arrays?
 
 ReadfileAndCopyContentIntoArray.d
 import std.stdio;

 int lineNumber = 0;
 char[][int] fileInArray;

 void main(){
     File exampleFile = File("exampleText.txt");
     foreach(line; exampleFile.byLine){

         lineNumber++;
         fileInArray[lineNumber] ~= line;

     }
     writeln(fileInArray);
 }
I have to ask because I don't know if this is similar to your true use case or not -- but why would you use an AA when you have an ordered list with keys that go from 0 to N? Why not just use an array? As others have said, RedBlackTree can be used as an ordered map (though this requires some definition of a mapping on top of it). -Steve
Jun 02 2020