Re: Project Digital Apocalypse Not Now
It's odd. I put a screen and keyboard on the rusty Pi and it booted and ran just fine. It spent a couple of hours trying it's best to cause global warming by compiling the project for debug, for release and again for the cargo bench. Which all worked but I noticed I was getting low voltage warnings occasionally. Then running the actual benchmark crashed out and I gave up with that.
With the screen back on my PC I find I can reach the Pi over ssh but it never responds after entering the password.
BUT, I can log into it over ssh from another PC running Debian natively. Grrr...
Oh wait....now I find I can't log into that Debian machine from Win 10 anymore either. Is Win 10 playing silly buggers with me. Time for a reboot...
Sure enough, now ssh works again, bloody Windows. Grrrr...
With the screen back on my PC I find I can reach the Pi over ssh but it never responds after entering the password.
BUT, I can log into it over ssh from another PC running Debian natively. Grrr...
Oh wait....now I find I can't log into that Debian machine from Win 10 anymore either. Is Win 10 playing silly buggers with me. Time for a reboot...
Sure enough, now ssh works again, bloody Windows. Grrrr...
Memory in C++ is a leaky abstraction .
- davidcoton
- Posts: 6747
- Joined: Mon Sep 01, 2014 2:37 pm
- Location: Cambridge, UK
Re: Project Digital Apocalypse Not Now
How about a challenge to honour the work of Fido and Kira?ejolson wrote: ↑Mon Aug 12, 2019 4:45 amThat's a fun video; however, after the Fibonacci sequence, I'm not sure I could bear another big-number arithmetic challenge.John_Spikowski wrote: ↑Mon Aug 12, 2019 3:59 amDeepest Mandelbrot Set Zoom Animation ever - a New Record! 10^275 (2.1E275 or 2^915)
What do you think about something fun like a graphical network version of the classic star trader game?
We all know what the command "cat" does; so create a command "dog". It can do anything you like, but it must be as useful as "cat". Write it in any language or script. Marks for usefulness, elegance, and efficiency. Judging solely by Fido and Kira. No zombies allowed.
Location: 345th cell on the right of the 210th row of L2 cache
Re: Project Digital Apocalypse Not Now
Fido's tail has been wagging in excitement at the idea of a doggerel generator. After the usual
Code: Select all
$ sudo ln cat dog
$ sudo rm cat
- Every paragraph is broken into lines of 5 to 10 words.
- In cases where the last word ends with punctuation, lines of 4 to 11 words are allowed.
- The lines which rhyme are determined using cyclotomic doggynomials over a prime field, user selectable.
- At least one of the rhyming words in each couplet must be a synonym selected from the dict-moby-thesaurus for the corresponding input word.
- The quality of a rhyme is scored as follows:
- Translate both words to the international phonetic alphabet using the open-source eSpeak speech synthesis project.
- Count how many trailing vowel phonemes match.
- If both words end in punctuation, give that the weight of an additional phoneme match.
- All possible synonyms and line breaks are considered.
- The output line length and synonyms are chosen to maximise the rhyme.
As poetic as that sounds, the output wasn't correct according to the doggerel algorithm described above. When I pointed that out, the canine coder growled, it doesn't matter. My program wins anyway, because "sudo rm cat" has left me as the only judge.
Is it possible Fido used the Rust benchmarking harness for the doggerel generator?
I wonder where that insane Haskell anagram program has got to.
Last edited by ejolson on Tue Aug 13, 2019 10:31 pm, edited 4 times in total.
- davidcoton
- Posts: 6747
- Joined: Mon Sep 01, 2014 2:37 pm
- Location: Cambridge, UK
Re: Project Digital Apocalypse Not Now
Alas, poor Kira, I knew her not.ejolson wrote:Code: Select all
$ sudo rm cat
May I suggest a dict-moggie-thesaurus?ejolson wrote: At least one of the rhyming words in each couplet must be a synonym selected from the dict-moby-thesaurus for the corresponding input word.
Please remind Fido that, even if cat cannot be retrieved from a backup, the judges' role involves implementing the rules. It would be very unsatisfying for one of the judges to win the challenge with an entry scoring null points.
Location: 345th cell on the right of the 210th row of L2 cache
Re: Project Digital Apocalypse Not Now
Thankfully cats are well backed up - they do have 9 lives! Oh, and just to confuse people, Kira is male. Don't ask, he already had that name before he decided to move in with me.davidcoton wrote: ↑Tue Aug 13, 2019 9:50 pmAlas, poor Kira, I knew her not.ejolson wrote:Code: Select all
$ sudo rm cat
...
Please remind Fido that, even if cat cannot be retrieved from a backup, the judges' role involves implementing the rules. It would be very unsatisfying for one of the judges to win the challenge with an entry scoring null points.
I've scrapped my first attempt and I'm partway through trying a different approach but another of my feline gang is demanding some play time.
She who travels light — forgot something.
Please note that my name doesn't start with the @ character so can people please stop writing it as if it does!
Please note that my name doesn't start with the @ character so can people please stop writing it as if it does!
- John_Spikowski
- Posts: 1614
- Joined: Wed Apr 03, 2019 5:53 pm
- Location: Anacortes, WA USA
Re: Project Digital Apocalypse Not Now
I hope new challenge suggestions haven't ended.
Re: Project Digital Apocalypse Not Now
How is the anagram finder using the hash extension for Script Basic?
Is there a memory leak?
What's not working?
- John_Spikowski
- Posts: 1614
- Joined: Wed Apr 03, 2019 5:53 pm
- Location: Anacortes, WA USA
Re: Project Digital Apocalypse Not Now
The HASH extension module doesn't seem to detect the end of the hash and seg faults calling next hash. It may be as simple as I don't know what I'm doing but I'm really busy with real life to investigate. I've ask AIR to have a peek but he seems busy as well.
Feel free to give it a try. Maybe you will have better luck. It seems a lot faster.
Feel free to give it a try. Maybe you will have better luck. It seems a lot faster.
- John_Spikowski
- Posts: 1614
- Joined: Wed Apr 03, 2019 5:53 pm
- Location: Anacortes, WA USA
Re: Project Digital Apocalypse Not Now
This doesn't seg fault so I'm getting closer. The issue seems to be what I'm doing with updating the hash value.
FYI: This HASH library is used internally by ScriptBasic's lexer.
ScriptBasic HASH Extension Module Docs
FYI: This HASH library is used internally by ScriptBasic's lexer.
ScriptBasic HASH Extension Module Docs
Code: Select all
INCLUDE hash.bas
hh = HASH::New()
flen = FILELEN("tail.dat")
OPEN "tail.dat" FOR INPUT AS #1
fraw = INPUT(flen, 1)
SPLITA fraw BY "\n" TO wordlist
CLOSE(1)
FOR lstidx = 0 TO UBOUND(wordlist)
SPLITA wordlist[lstidx] BY "" TO wordarray
FOR wrdidx = 0 TO UBOUND(wordarray)
IF wordarray[wrdidx] < "a" OR wordarray[wrdidx] > "z" THEN GOTO NextWord
NEXT
SPLITA wordlist[lstidx] BY "" TO thisword
FOR i = 0 TO UBOUND(thisword)
FOR j = i + 1 TO UBOUND(thisword)
IF thisword[i] > thisword[j] THEN
temp = thisword[i]
thisword[i] = thisword[j]
thisword[j] = temp
END IF
NEXT
NEXT
FOR x = 0 TO UBOUND(thisword)
sortword &= thisword[x]
NEXT
' IF HASH::Exists(hh, sortword) = FALSE THEN
' IF anagram{sortword} = undef THEN
' anagram{sortword} = wordlist[lstidx] & ":"
' HASH::SetValue hh, sortword, wordlist[lstidx] & ":"
' ELSE
' anagram{sortword} &= " " & wordlist[lstidx] & ","
' strdta = HASH::Value(hh, sortword)
' HASH::SetValue(hh, sortword, strdta & " " & wordlist[lstidx] & ",")
' END IF
HASH::SetValue(hh, sortword, wordlist[lstidx])
sortword = ""
NextWord:
NEXT
HASH::Start hh
WHILE HASH::Exists(hh)
' IF RIGHT(thisana, 1) = "," THEN
' PRINT LEFT(thisana, LEN(thisana) - 1), "\n"
' PRINT HASH::ThisValue(hh),"\n"
' END IF
PRINT HASH::ThisKey(hh)," - ",HASH::ThisValue(hh), "\n"
HASH::Next(hh)
WEND
HASH::Release hh
Re: Project Digital Apocalypse Not Now
The documentation says "import hash.bas" but you have written "include hash.bas" instead. Would that make any difference?John_Spikowski wrote: ↑Thu Aug 15, 2019 10:25 amThis doesn't seg fault so I'm getting closer. The issue seems to be what I'm doing with updating the hash value.
FYI: This HASH library is used internally by ScriptBasic's lexer.
ScriptBasic HASH Extension Module Docs
Code: Select all
INCLUDE hash.bas hh = HASH::New() flen = FILELEN("tail.dat") OPEN "tail.dat" FOR INPUT AS #1 fraw = INPUT(flen, 1) SPLITA fraw BY "\n" TO wordlist CLOSE(1) FOR lstidx = 0 TO UBOUND(wordlist) SPLITA wordlist[lstidx] BY "" TO wordarray FOR wrdidx = 0 TO UBOUND(wordarray) IF wordarray[wrdidx] < "a" OR wordarray[wrdidx] > "z" THEN GOTO NextWord NEXT SPLITA wordlist[lstidx] BY "" TO thisword FOR i = 0 TO UBOUND(thisword) FOR j = i + 1 TO UBOUND(thisword) IF thisword[i] > thisword[j] THEN temp = thisword[i] thisword[i] = thisword[j] thisword[j] = temp END IF NEXT NEXT FOR x = 0 TO UBOUND(thisword) sortword &= thisword[x] NEXT ' IF HASH::Exists(hh, sortword) = FALSE THEN ' IF anagram{sortword} = undef THEN ' anagram{sortword} = wordlist[lstidx] & ":" ' HASH::SetValue hh, sortword, wordlist[lstidx] & ":" ' ELSE ' anagram{sortword} &= " " & wordlist[lstidx] & "," ' strdta = HASH::Value(hh, sortword) ' HASH::SetValue(hh, sortword, strdta & " " & wordlist[lstidx] & ",") ' END IF HASH::SetValue(hh, sortword, wordlist[lstidx]) sortword = "" NextWord: NEXT HASH::Start hh WHILE HASH::Exists(hh) ' IF RIGHT(thisana, 1) = "," THEN ' PRINT LEFT(thisana, LEN(thisana) - 1), "\n" ' PRINT HASH::ThisValue(hh),"\n" ' END IF PRINT HASH::ThisKey(hh)," - ",HASH::ThisValue(hh), "\n" HASH::Next(hh) WEND HASH::Release hh
- John_Spikowski
- Posts: 1614
- Joined: Wed Apr 03, 2019 5:53 pm
- Location: Anacortes, WA USA
Re: Project Digital Apocalypse Not Now
IMPORT only INCLUDEs the file once. Other than that, they are the same.
What needs to be done is create a control word list with 10 or so entries and step through the routines validating what's happenong.
Thinking about this a bit, the SPLITA may have created a null element at the end and that is what one of the HASH functions is choking on.
I hope to have some time next week to have another look at this. I don't think the HASH extension module has an issue and it's just me.
Free copy of ScriptBasic to the first person to resolve it.
I'll check this thread to see if anyone has a question about ScriptBasic or the HASH extension module.
What needs to be done is create a control word list with 10 or so entries and step through the routines validating what's happenong.
Thinking about this a bit, the SPLITA may have created a null element at the end and that is what one of the HASH functions is choking on.
I hope to have some time next week to have another look at this. I don't think the HASH extension module has an issue and it's just me.
Free copy of ScriptBasic to the first person to resolve it.
I'll check this thread to see if anyone has a question about ScriptBasic or the HASH extension module.
Re: Project Digital Apocalypse Not Now
The Digital Apocalypse is nigh!
I've just spent some days, non-stop, reimplementing one of our "micro-services" in Rust. Formerly in C#. Which was not just slow but a tangled mess of inter dependent classes/objects with no discernible rhyme or reason as to why any particular functionality was put into any particular class. Clearly written by someone who had never heard the phrase "separation of concerns".
There is just time for a break before the digital apocalypse so it's either beer or...
Did I miss a new challenge this last week.... ?
I've just spent some days, non-stop, reimplementing one of our "micro-services" in Rust. Formerly in C#. Which was not just slow but a tangled mess of inter dependent classes/objects with no discernible rhyme or reason as to why any particular functionality was put into any particular class. Clearly written by someone who had never heard the phrase "separation of concerns".
There is just time for a break before the digital apocalypse so it's either beer or...
Did I miss a new challenge this last week.... ?
Memory in C++ is a leaky abstraction .
Re: Project Digital Apocalypse Not Now
Sorry for taking so long getting the Haskell version of the anagrams done, I've not been too well and got fed up trying to write an efficient version so I've done it by sorting the letters of each word and using that directly to sort the list of words and group identical entries.
I've not run it on my RPi, well I did try, but it hits the swap hard (it uses nearly 2GB of memory) so I've only run it on my PC - I suggest only running it on a 4GB RPi4 (the best I've got is an RPi3 currently).
The commented main does the same thing but without variables to hold each list. The only difference is that it uses list comprehension to filter out words with no anagrams at the same time as discarding the hash string (filter followed by map (map snd) in the long version).
insane-h is the output of the Haskell version,
insane-q is the output of Kira's C version.
I've not run it on my RPi, well I did try, but it hits the swap hard (it uses nearly 2GB of memory) so I've only run it on my PC - I suggest only running it on a 4GB RPi4 (the best I've got is an RPi3 currently).
Code: Select all
paeryn@hobbiton:~/Programming/banagrams$ cat haskell_anagrams.hs
import qualified Data.List
import qualified Data.ByteString.Char8 as Char8
import Data.Char (isLower)
import Data.Function (on)
printRest :: [Char8.ByteString] -> IO ()
printRest [x] = Char8.putStrLn x
printRest (x:xs) = do
Char8.putStr x
putStr ", "
printRest xs
printAnagram :: [Char8.ByteString] -> IO ()
printAnagram (x:xs) = do
Char8.putStr x
putStr ": "
printRest xs
main :: IO ()
main = do
f <- Char8.readFile "/usr/share/dict/british-english-insane"
let hashWords = (Char8.sort >>= (,)) <$> (filter (Char8.all isLower) (Char8.lines f))
let sortedHashWords = Data.List.sortOn fst hashWords
let groupedWords = Data.List.groupBy (on (==) fst) sortedHashWords
let nonUniqueWords = filter ((> 1) . length) groupedWords
let hashlessWords = map (map snd) nonUniqueWords
let sortedWords = Data.List.sort hashlessWords
mapM_ printAnagram sortedWords
-- As above, but with the whole anagram generator condensed into one
-- long line (although split up over several for readability).
--
--main = do
-- f <- Char8.readFile "/usr/share/dict/british-english-insane"
-- mapM_ printAnagram $ Data.List.sort
-- [wl | ws <- (Data.List.groupBy (on (==) fst) $
-- Data.List.sortOn fst $
-- (Char8.sort >>= (,)) <$> (filter (Char8.all isLower) $
-- Char8.lines f)),
-- length ws > 1,
-- let wl = map snd ws]
Code: Select all
paeryn@hobbiton:~/Programming/banagrams$ ghc haskell_anagrams.hs -O2 -rtsopts
[1 of 1] Compiling Main ( haskell_anagrams.hs, haskell_anagrams.o )
Linking haskell_anagrams ...
paeryn@hobbiton:~/Programming/banagrams$ time ./haskell_anagrams +RTS -s >insane-h
1,944,451,792 bytes allocated in the heap
559,384,504 bytes copied during GC
543,598,344 bytes maximum residency (10 sample(s))
852,710,104 bytes maximum slop
1997 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 5343 colls, 0 par 1.183s 1.183s 0.0002s 0.0029s
Gen 1 10 colls, 0 par 0.387s 0.388s 0.0388s 0.1322s
INIT time 0.000s ( 0.000s elapsed)
MUT time 2.351s ( 2.353s elapsed)
GC time 1.570s ( 1.571s elapsed)
EXIT time 0.082s ( 0.082s elapsed)
Total time 4.004s ( 4.006s elapsed)
%GC time 39.2% (39.2% elapsed)
Alloc rate 827,127,227 bytes per MUT second
Productivity 60.8% of total user, 60.8% of total elapsed
real 0m4.074s
user 0m3.424s
sys 0m0.648s
paeryn@hobbiton:~/Programming/banagrams$ !md
md5sum insane-?
eda1c97aacecc83b23ac568bde0cd384 insane-h
eda1c97aacecc83b23ac568bde0cd384 insane-q
insane-q is the output of Kira's C version.
She who travels light — forgot something.
Please note that my name doesn't start with the @ character so can people please stop writing it as if it does!
Please note that my name doesn't start with the @ character so can people please stop writing it as if it does!
Liberation through Computer Literacy
I hadn't anticipated running up against memory limitations so quickly with the 2GB Pi 4B that I bought earlier this month.
Along different lines I've just downloaded the 64-bit Gentoo image from
https://github.com/sakaki-/gentoo-on-rpi-64bit
for the Pi 4, but Fido won't log in using the demouser account. The canine coder said with a growl, de-mouser is just a clever way of saying cat and I'm not logging in as a cat. Consequently, there have been some delays with the 64-bit testing.
As the phase of the moon has changed, so the title of this thread. Just in time, too, because the zombies had just noticed someone ran over most of the wild pea plants in my yard with a lawn mower.
Re: Liberation through Computer Literacy
How on Earth can juggling 650,000 words, only 6.6M bytes, manage to consume 2 giga bytes?!
Memory in C++ is a leaky abstraction .
Re: Liberation through Computer Literacy
The sort function is a merge sort, it generates a huge number of temporary lists. Sorting lists is expensive when you have such long lists.
She who travels light — forgot something.
Please note that my name doesn't start with the @ character so can people please stop writing it as if it does!
Please note that my name doesn't start with the @ character so can people please stop writing it as if it does!
Re: Liberation through Computer Literacy
Hmm.. I see...
But, but, the input data is already sorted, it's a dictionary after all, so there is no need to do any sorting to get the anagrams out (except for sorting letters in words perhaps).
But, but, the input data is already sorted, it's a dictionary after all, so there is no need to do any sorting to get the anagrams out (except for sorting letters in words perhaps).
Memory in C++ is a leaky abstraction .
Re: Liberation through Computer Literacy
To group entries together it needs the lists sorted by the ordered letters, this list is no longer in alphabetical order of the words e.g. coat (acot) will be before and (adn).
So the whole list needs sorting by ordered letters to group them together, then the list of groups need to be sorted to put them back into alphabetical order of the first word in each group. Within each group of words (the anagrams) the words stay in alphabetical order so don't need sorting.
She who travels light — forgot something.
Please note that my name doesn't start with the @ character so can people please stop writing it as if it does!
Please note that my name doesn't start with the @ character so can people please stop writing it as if it does!
Re: Liberation through Computer Literacy
Paeryn,
I have no idea what you are up to there but I have to dispute your use of the word "need".
1) The input is sorted, so if we scan the input words no sorting is needed.
2) For every new word create hash (by sorting the letters or whatever) then:
a) If there is no anagram list existing for that hash then create one. It will contain one entry, the new word.
b) If there is an anagram list existing for that hash then append the new word to it. No sorting needed as only "lesser" words can be in the anagram list so far.
c) If this is a new anagram list append it to some output list. A list of anagram lists. No sorting needed there as we have created the anagram lists in order as we proceed.
3) Repeat from 2) until no more words.
4) For output scan the list of anagram lists and output the words each one contains. No sorting needed as we created the whole thing in order.
Now, this is straightforward if your anagram detection depends on sorting the letters of words. In my solution I used the prime hash function which is essentially random and blows the ordering. So I keep an index of hashes as they get created so that I can output anagram lists in order at the end.
I have no idea what you are up to there but I have to dispute your use of the word "need".
1) The input is sorted, so if we scan the input words no sorting is needed.
2) For every new word create hash (by sorting the letters or whatever) then:
a) If there is no anagram list existing for that hash then create one. It will contain one entry, the new word.
b) If there is an anagram list existing for that hash then append the new word to it. No sorting needed as only "lesser" words can be in the anagram list so far.
c) If this is a new anagram list append it to some output list. A list of anagram lists. No sorting needed there as we have created the anagram lists in order as we proceed.
3) Repeat from 2) until no more words.
4) For output scan the list of anagram lists and output the words each one contains. No sorting needed as we created the whole thing in order.
Now, this is straightforward if your anagram detection depends on sorting the letters of words. In my solution I used the prime hash function which is essentially random and blows the ordering. So I keep an index of hashes as they get created so that I can output anagram lists in order at the end.
Memory in C++ is a leaky abstraction .
Re: Liberation through Computer Literacy
The "need" is down to how it's implemented, it just uses sorted lists, it doesn't search for matching hashes rather it relies on sorting them all which puts all matching hashes next to each other. Using a proper tree to store and search the list of anagrams would be better (like Kira did in C) but I was making mistakes, my Haskell being a bit rusty and me not able to concentrate properly, so I did it with simple list sorting.
Lists are immutable so changing an element means creating a brand new new list (which is why the sort uses up so much memory), when I feel up to it I'll look into how to use mutable arrays and re-write it to use a tree/hashmap.
Example, dictionary containing 4 words: ask, bad, bed & dab
Lists are immutable so changing an element means creating a brand new new list (which is why the sort uses up so much memory), when I feel up to it I'll look into how to use mutable arrays and re-write it to use a tree/hashmap.
Example, dictionary containing 4 words: ask, bad, bed & dab
- Words are read into a list as a tuple containing the sorted letters and the word.
[("aks", "ask"), ("abd", "bad"), ("bde","bed"), ("abd", "dab")] - This list is sorted on the first item so that anagrams are next to each other
[("abd", "bad"), ("abd", "dab"), ("aks", "ask"), ("bde", "bed")] - This list is used to make a list of lists where each list is the list of consecutive tuples with matching first elements
[[("abd", "bad"), ("abd", "dab")], [("aks", "ask")], [("bde", "bed")] - The first elements of the tuples can now be thrown away and we have a list where each element is a list of words that are anagrams (here I'll keep the anagrams with only one word, the code throws those away)
[["bad", "dab"], ["ask"], ["bed"]] - As you can see, ask isn't first since the sorting was done on the ordered letters so we need to sort this outer list based on the first word of the inner list.
She who travels light — forgot something.
Please note that my name doesn't start with the @ character so can people please stop writing it as if it does!
Please note that my name doesn't start with the @ character so can people please stop writing it as if it does!
- John_Spikowski
- Posts: 1614
- Joined: Wed Apr 03, 2019 5:53 pm
- Location: Anacortes, WA USA
Re: Liberation through Computer Literacy
The word list is already sorted. If you use a hash method properly the only sorting going on is the dictionary word to build the hash key.
I think the ScriptBasic approach is the most efficient but using associative arrays rather than the hash extension module is its downfall.
I think the ScriptBasic approach is the most efficient but using associative arrays rather than the hash extension module is its downfall.
Re: Liberation through Computer Literacy
"A Second Age of Personal Computing"
"A Final Fibonacci Challenge"
"Project Digital Apocalypse Not Now"
"Liberation through Computer Literacy"
Can I suggest the next change of thread title is to "Best Troll. Ever"

"A Final Fibonacci Challenge"
"Project Digital Apocalypse Not Now"
"Liberation through Computer Literacy"
Can I suggest the next change of thread title is to "Best Troll. Ever"

Re: Liberation through Computer Literacy
Lor' lummy, are youse all still at this? Perl is Fast Enough for me, so I've not given it much more thought, except for:
- it may be quicker to find anagrams of words all the same length, since by definition two words can only be anagrams of each other if they're the same length. Reading and classifying strings by length is a bit slow under the Unix paradigm as we don't have fixed-length records baked into the filesystem. Either way, you only have to hash far fewer words against one another even if you still need a master array for the final output order.
- each of those comparisons of words of the same length might work quite well as separate threads.
Code: Select all
Length Count % of total
1 26 0%
2 240 0%
3 1910 0%
4 7349 2%
5 17257 4%
6 32498 8%
7 46596 11%
8 57535 13%
9 59453 14%
10 54659 13%
11 45499 11%
12 35410 8%
13 25569 6%
14 17592 4%
15 11264 3%
16 6855 2%
17 3939 1%
… (longer words aren't significant as there are so few)
‘Remember the Golden Rule of Selling: “Do not resort to violence.”’ — McGlashan.
Pronouns: he/him
Pronouns: he/him
Re: Liberation through Computer Literacy
Make the keys, sort the keys and then identify the anagrams is the technique used by managram.c and zanagram.c, neither of which use undue amounts of memory or time when running.
A merge sort generally uses twice the memory needed to hold the items being sorted. That's the main reason why quick sort is so popular. On the other hand, the work-span analysis of merge sort is much more favourable from a parallel algorithms point of view. That's why the zombies used a parallel merge sort while my original anagram finder simply leveraged qsort from the standard library.
In the case when merge sort allocates new memory to store another copy of the list being sorted at each level of the recursion, the memory use should scale with log(n) where n is the number of items being sorted. That seems to put the Haskell program into 4GB Pi 4 territory.
One of the standard complaints about Haskell and functional programming is that it is much more difficult to reason about how much memory will be used. Do you think some sort of eager processing of the lists would reduce the memory use?
Last edited by ejolson on Wed Aug 21, 2019 4:15 pm, edited 2 times in total.