How much memory may a HPPL program use on a G2?

[Tyann]

Très intéressant, mais pour des listes de chaînes ?

Very interesting, but for channel lists?

[komame]

(09-09-2023 10:57 AM)Tyann Wrote:  Very interesting, but for channel lists?

Could you provide more details about the case that interests you? Perhaps an example to help me understand better?

[komame]

Hi Stefan,

(09-09-2023 10:50 AM)Stefan Falk Wrote:  In this specific program, I only need to know if or of not a given solution was already found (just rotated or mirrored), but the number of that existing solution is only interesting for displaying it. Also, all of my substrings would be of the same size, so I could easily compute the solution number from the INSTR position.

I've already modified the implementation of your algorithm on my HP Prime by editing a few lines of code, so I know the test results The execution time of the QUEENS algorithm increases exponentially with the size of the board. For a 12x12 board, there are over 14,000 solutions, for 13x13 over 73,000, and for 14x14, it already exceeds 350,000. The computation time on a real HP Prime takes several hours. Even on the emulator, it took a long time (if I remember correctly, it was about 1.5-2 hours), but eventually, I managed to get the result for 14x14.

In my opinion, the program itself needs optimization because it redraws the solution from scratch each time, which significantly slows down the program. You should draw the board once, buffer it in G1, and then use BLIP_P to draw it 'in one go' while changing the presentation of solutions in each iteration. This should greatly reduce the time needed to find a solution.

(09-09-2023 10:50 AM)Stefan Falk Wrote:  Something like a hash table does not exist in the Prime, does it?

Unfortunately not.

[Tyann]

J'ai utilisé des grandes listes de chaînes pour une application de dictionnaire.
Une liste de sous listes par nombre de lettres.
pour 2 lettres 1 seule sous liste, pour 10 lettres quelque chose comme 7 ou 8 sous listes.
Lorsque je suis passé sur G2, j'ai remarqué tout de suite un problème de vitesse par rapport à G1.
J'ai résolu une partie du problème en stockant les listes dans des AVars au lieu des AFiles.
Je vais essayer de convertir mes listes en STRING tout simplement avant de les renvoyer depuis un sous programme pour voir si je gagne du temps.

I used large lists of strings for a dictionary application.
A list of sub-lists by number of letters.
for 2 letters 1 single sub-list, for 10 letters something like 7 or 8 sub-lists.
When I switched to G2, I immediately noticed a speed problem compared with G1.
I solved part of the problem by storing the lists in AVars instead of AFiles.
I'm going to try converting my lists to STRING simply before sending them back from a sub-program to see if I save time.

[komame]

(09-09-2023 12:09 PM)Tyann Wrote:  I used large lists of strings for a dictionary application.
A list of sub-lists by number of letters.
for 2 letters 1 single sub-list, for 10 letters something like 7 or 8 sub-lists.

Unfortunately, I still don't fully understand your problem from this description. Could you provide an example of such a list with sublists for a few values to better illustrate your issue?

[Tyann]

Le problème principal est la vitesse d'exécution dans certains cas.
l'application permet par exemple de vérifier si un mot est correctement orthographié.
Avec POS le résultat est instantané.
L'application permet aussi de rechercher des mots avec des lettres manquantes pour résoudre
des grilles de mots croisés par exemple.
Eh bien là j'ai remarqué que si la fonction renvoie une grande liste de réponses possibles, le retour de la fonction prend un temps important, bien sûr la recherche prends du temps aussi mais là c'est normal.
Pour ce qui est des listes, elles contiennent tout simplement les mots du dictionnaire sous forme de chaînes.

The main problem is speed of execution in certain cases.
For example, the application can be used to check whether a word is spelt correctly.
With POS, the result is instantaneous.
The application can also be used to search for words with missing letters to solve crossword puzzles, for example.

Well, I've noticed that if the function returns a large list of possible answers, the function takes a long time to return, and of course the search takes time too, but that's normal.
As for the lists, they simply contain the words in the dictionary in the form of strings.

[komame]

If I understand correctly, your application contains one main list, and within it, there are sublists where each of them contains words of a specific length. So, the first sublist contains words of length 2 characters, the second sublist contains words of length 3 characters, and so on. Is that correct?
There are two ways to use the program.
1. The first is when someone provides a word as input, and based on its length, you search the appropriate list and return information that such a word exists (is spelled correctly).
2. The second way of using it is when the word has missing letters. In this case, you iterate through the list for words of a specific length and verify the match of each word with the given pattern. If it matches, you retrieve that word as a result, and then continue searching for others until the end of the list.
Is that how your program works?

[Tyann]

Oui c'est à peu prés cela, sauf qu'il y a une liste de sous listes pour les mots de 2 lettres , une liste de sous listes pour les mots de 3 lettres etc...
La AVars("N9") par exemple contient 50 183 mots répartis sur 6 sous listes.
Même si il y a moins de 10000 mots ils sont quand même dans une sous liste, pour que la fonction de recherche utilise toujours le même principe une boucle FOR de 1 à nombre de sous listes, puis recherche par sous listes.
Il y a des fonctions EXPORT également : comme une qui renvoie un mot au hasard d'un nombre de lettres spécifiées ou d'un nombre de lettres mini ou quelconque.
J'ai utilisé cette fonction pour un programme de 'pendu' par exemple.
J'ai encore beaucoup choses à faire et beaucoup de mots à enregistrer, c'est un 'travail de longue haleine' mais passionnant.

Yes, that's about it, except that there is a list of sub-lists for words of 2 letters, a list of sub-lists for words of 3 letters etc...
The AVars ("N9") for example contains 50,183 words spread over 6 sub-lists.
Even if there are less than 10000 words, they are still in a sub-list, so the search function always uses the same principle: a FOR loop from 1 to the number of sub-lists, then search by sub-list.
There are EXPORT functions too: like one that returns a random word of a specified number of letters or a minimum or any number of letters.
I used this function for a 'hangman' program, for example.
I still have a lot of things to do and a lot of words to record, it's a 'long job' but exciting.

[komame]

(09-09-2023 03:07 PM)Tyann Wrote:  The AVars ("N9") for example contains 50,183 words spread over 6 sub-lists.
Even if there are less than 10000 words, they are still in a sub-list, so the search function always uses the same principle: a FOR loop from 1 to the number of sub-lists, then search by sub-list.

So now, when someone provides a word with missing letters, does your algorithm search through all the words in all 6 lists and even compare them to words of different lengths? If that's the case, it explains the performance issue you're facing. If you were to divide these lists based on word length, I suspect the speed of operation would be much higher.
Let's assume you have a list of lists with words like this:

{
  { }, //stays empty because there is no one-letter words
  { "aa", "ab", "bc", "cd" ... },
  { "aaa", "abc", "bde", "cad" ... },
  { "abcd, "bcde", "cbde", "dbfe" ... },
  { ..... }
}

When someone searches for a word, you can perform the search that way:
main_list => the main list divided into sublists based on the word length.
search_for => the searched word

Code:

POS(main_list(DIM(search_for)),search_for)

This will search only the specific list for the given word length.
Then you don't need to iterate through all the lists; the search will immediately occur in the correct list where the result is guaranteed. The algorithm won't search through the remaining lists because it doesn't make sense to do so.

This optimization, especially for matches with missing letters, could significantly speed up the process. Additional, for matches with missing letters it's important to copy the target sublist to a local variable. These lists will be much shorter than what you currently have, so I suspect it will perform faster than using AVars with big list.

The point is that working with small, well-divided lists in PPL is much faster than with large lists. If possible, they should be divided.
It may turn out that such optimization is sufficient, and you won't even need to change from using PPL lists to emulating using strings.

[Tyann]

Bonjour

Lors d'une recherche des mots avec des lettres manquantes, je ne cherche que dans la liste des mots de même longueur.
Par exemple si j'entre PL???E?, la recherche se fera uniquement dans AVars("N7").
Oui je recherche directement dans AVar car je pense que recopier les sous listes dans une variable locale pourrait prendre du temps inutilement.
Je ferai un essai cependant pour voir ce qui ce passe, merci pour la suggestion.


Hello

When searching for words with missing letters, I only search in the list of words of the same length.
For example, if I enter PL???E?, the search will only be done in AVars("N7").
Yes, I search directly in AVar because I think that copying the sub-lists into a local variable could take up unnecessary time.
I'll give it a try though to see what happens, thanks for the suggestion.

[komame]

(09-10-2023 05:42 AM)Tyann Wrote:  When searching for words with missing letters, I only search in the list of words of the same length.
For example, if I enter PL???E?, the search will only be done in AVars("N7").
Yes, I search directly in AVar because I think that copying the sub-lists into a local variable could take up unnecessary time.

I apologize; I didn't understand your explanations earlier. If the lists are divided based on word length and you keep them in AVars, that's a good solution, and there's no need for you to change it. Could you please explain how you check for word matches with missing letters? Do you iterate through individual letters and compare the n-th letter of the search word with the n-th letter of the word on the list, or do you do it differently?
And a very important thing: are the words on the lists sorted, or are they entered in random order?

I have a preliminary implementation ready using string-based lists, but before I show it to you, please answer my questions.

[Tyann]

Je suppose que le traducteur n'aide pas toujours à la bonne compréhension.

Pour la recherche je compare lettre par lettre, si la lettre est = ou si c'est un joker '?' je continue
et à la fin de boucle j' ajoute le mot à la liste de solutions, si la lettre est <> je passe au mot suivant directement.
J'ai trié les listes avec l'idée de tester si les premières lettres du mot sont connues, si elles sont > au dernier mot de chaque sous liste, je passe à la sous liste suivante et ne teste aucun mot (c'est en cours).
Pour être complet je dois préciser que j'enregistre les mots en minuscules avec les accents.
Donc quand je fais une recherche pour 'mots croisés' je convertit les mots en MAJUSCULES sans accents et cela consomme du temps également.

I suppose that the translator doesn't always help with understanding.

For the search I compare letter by letter, if the letter is = or if it's a wildcard '?' I continue
and at the end of the loop I add the word to the list of solutions, if the letter is <> I go directly to the next word.
I've sorted the lists with the idea of testing whether the first letters of the word are known. If they are > the last word in each sub-list, I move on to the next sub-list and don't test any words (this is in progress).
For the sake of completeness, I should point out that I record words in lower case with accents.
So when I do a search for 'crosswords' I convert the words to UPPERCASE without accents and that takes time too.

[komame]

(09-10-2023 11:12 AM)Tyann Wrote:  For the sake of completeness, I should point out that I record words in lower case with accents.
So when I do a search for 'crosswords' I convert the words to UPPERCASE without accents and that takes time too.

I don't understand the conversion of accented letters to letters without accents. For instance, if you have the word "forêt" in a crossword puzzle, where the missing letter pattern in the crossword looks like this: "f??ê?" the algorithm will find other words that have the letter "e" in place of "ê" and they won't fit the crossword. What is the purpose of this conversion?
Maybe I misunderstood something again?

And one more thing: You mentioned that you have over 50,000 words of 9-letter length in your dictionary. How much time does your program currently need to return a result for this length (optimistically, on average, and pessimistically)?

[Tyann]

Bonjour

Pour les mots croisés, les grilles sont formées avec des lettres MAJUSCULES sans accents, donc si dans la grille j'ai un F 2 cases vides puis un E et une case vide, j'entre f??e? , le programme me renvoie comme solutions entre autres 'forêt' et 'furet' .
Peut être pas évident avec un traducteur.

Pour les temps d'exécution, j'ai encore quelques pistes d'optimisation à testé avant de vous répondre.


Hello

For crosswords, the grids are formed with UPPERCASE letters without accents, so if in the grid I have an F 2 empty squares then an E and an empty square, I enter f??e? the programme returns 'forest'(forêt) and 'ferret'(furet) as solutions.
Maybe not obvious with a translator.

As far as execution times are concerned, I've still got a few optimisation ideas to test before giving you an answer.

[komame]

(09-11-2023 05:39 AM)Tyann Wrote:  For crosswords, the grids are formed with UPPERCASE letters without accents, so if in the grid I have an F 2 empty squares then an E and an empty square, I enter f??e? the programme returns 'forest'(forêt) and 'ferret'(furet) as solutions.

I don't know your language, but in my native language, there are 9 diacritical marks (ą, ć, ę, ł, ń, ó, ś, ź, ż). They appear normally in crosswords, and you have to find an exact match for them. If in your language, crosswords always use letters without diacritics, then it's clear why you're doing this conversion. The question is, in such a situation, wouldn't it be better to have words in the dictionary with diacritics converted from the start? Searching in a dictionary without diacritics would be much faster. What about when a diacritical mark is the first letter of a word (if it can happen in your language)? In that case, it becomes even more complicated because you can't compare whether the last word in the list is smaller than what you're looking for to skip to the next list.
Anyway, I understand that during word comparison, you additionally iterate through the characters and sequentially replace diacritical marks with their Latin alphabet counterparts.

Best regards,

[komame]

Hi Tyann,

Could I please ask you to send me your word database? Any data format will do, it can be a text file, a snippet of your program, or a list. I want to perform tests on my solution along with accent conversion.

Thanks

[Tyann]

Bonjour
Ce sont des fichiers textes que j'ai trouvé sur le Web, je peux éventuellement vous les envoyer.
Je peut aussi vous fournir les liens où ils se trouvent, peut être plus facile.

Hello
These are text files I've found on the Web, so I may be able to send them to you.
I can also provide you with the links where they can be found, which might be easier.

[komame]

(09-11-2023 04:06 PM)Tyann Wrote:  I can also provide you with the links where they can be found, which might be easier.

Ok, I'll wait.

[Tyann]

Je voulais vérifier que j'avais encore le lien :

I wanted to check that I still had the link:

list words

[komame]

This website doesn't allow downloading the entire word dictionary. Even if you choose a specific word length, you have to download the dictionary for each letter of the alphabet separately. If I want to download words ranging from 2 to 10 letters, I would have to perform over 200 downloads. In this case, I will prepare a test and share the solution here only for 9-letter words.