Text Only | Text with Attachments

QB64.org Forum

Active Forums => QB64 Discussion => Topic started by: Larryrl on April 27, 2020, 12:48:20 am

Title: Help with an array
Post by: Larryrl on April 27, 2020, 12:48:20 am
I have some arrays for a program as is shown in the code below.


Code: QB64: [Select]
  1. dim language$(200000,3),ldup$(200000),edup$(200000)
  2.  

Now I need a loop or something to search the array and find duplicate entries. I need it to check every index against every other index of the language$ array for column 1 and also for column 2. Then if it finds more than one entry for a word in column 1 it should be put into the next unused index in the ldup array and if it finds duplicates in column 2, it should be put into the next unused index in the edup array. This program works with constructed languages or conlangs. I used to do this in ms excel where they have a highlight cells function that colors in the duplicate values. I do not need  the color part, I just want the words that are duplicated to get the proper ldpup, or edup array depending on if it is a language word or an English word.

This is the only part of the program that is still not functional. To be honest, it is not even written in QB64. But, when I can't see a solution beyond all of the windows controls and such of some of the other dialets of basic for windows, I always come back to normal basic like QB64. If necessary I can modify it and get it to work in the language it is in once I kind of get some idea of how to begin.
Title: Re: Help with an array
Post by: Pete on April 27, 2020, 05:15:02 am
This is the same as post: https://www.qb64.org/forum/index.php?topic=2469.0

I think this would demo in QB64 what you are trying to achieve in your Liberty Basic routine.

Code: QB64: [Select]
  1. DIM language$(20, 3), ldup$(20), edup$(20)
  2. language$(1, 1) = "cat"
  3. language$(2, 1) = "dog"
  4. language$(3, 1) = "turtle"
  5. language$(4, 1) = "frog"
  6. language$(5, 1) = "bird"
  7. language$(1, 2) = "cat"
  8. language$(2, 2) = "rabbit"
  9. language$(3, 2) = "dog"
  10. language$(1, 3) = "frog"
  11. language$(2, 3) = "snake"
  12.  
  13. FOR i = 1 TO 20
  14.     FOR j = 1 TO 3
  15.         IF language$(i, j) <> "" THEN
  16.             concat$ = concat$ + language$(i, j) + "|"
  17.         END IF
  18.     NEXT j
  20. ' PRINT concat$
  21. seed = 1
  23.     x$ = MID$(concat$, seed, INSTR(seed, concat$, "|") - seed)
  24.     ' PRINT x$
  25.     oldseed = seed
  26.     seed = INSTR(seed, concat$, "|") + 1
  27.     IF INSTR(MID$(concat$, seed), x$ + "|") THEN
  28.         IF INSTR(MID$(concat$, 1, oldseed), x$ + "|") = 0 THEN
  29.             ' Duplicate word found.
  30.             cnt1 = cnt1 + 1: ldup$(cnt1) = x$
  31.             dupconcat$ = dupconcat$ + x$ + "|"
  32.         END IF
  33.     ELSE
  34.         IF INSTR(dupconcat$, x$) = 0 THEN
  35.             ' Unique word found.
  36.             cnt2 = cnt2 + 1: edup$(cnt2) = x$
  37.         END IF
  38.     END IF
  39. LOOP UNTIL seed > LEN(concat$)
  40.  
  41. ' Okay, let's see the results.
  42. PRINT "[Duplicate Words]"
  43. FOR i = 1 TO cnt1
  44.     PRINT ldup$(i)
  47. PRINT "[Unique Words]"
  48. FOR i = 1 TO cnt2
  49.     PRINT edup$(i)

Title: Re: Help with an array
Post by: Larryrl on April 27, 2020, 01:20:59 pm

Checking for duplicate words problem solved!

Code: QB64: [Select]
  1. lindex=0:eindex=0
  2. i=0
  3.  
  4. while i<tw+1
  5. i=i+1
  6. for j=1 to tw
  7. if i<>j and language$(i,1)=language$(j,1) then lindex=lindex+1:ldup$(lindex)=language$(j,1)
  8. if i<>j and language$(i,3)=language$(j,3) then eindex=eindex+1:edup$(eindex)=language$(j,1)
  11.  
  12.  

Title: Re: Help with an array
Post by: Pete on April 27, 2020, 02:43:05 pm
I'd be interested to see  how long that takes, if you have the 200,000 elements as per your DIM statement indicates. Using two loops will require 200,000 x 200,000 or 40,000,000,000 passes to complete. That's why I prefer using INSTR; however, if it's just a one-time sort procedure, yep, I've had those too. You just let the app run until the job gets done. How much faster would INSTR be for something of this magnitude? I have no idea. It would be interesting to test out.

I did notice your post does not filter out placing duplicates into the new array multiple times. In other words, if cat occurred 30 times in the language array, it would be place 30 times in the dup array, instead of just once, to indicate it is present more than once in the language array. If that doesn't work for you as intended, you would need to loop through each of the dup arrays, and only add the duplicate entry if it wasn't already present.Using looping, that would greatly magnify the number of passes needed to complete the task. Again, using INSTR, even in that limited capacity, would speed up that filtering process.

Pete
Title: Re: Help with an array
Post by: TempodiBasic on April 27, 2020, 05:14:08 pm
@Pete

yes, math is not an opinion
Quote
Using two loops will require 200,000 x 200,000 or 40,000,000,000 passes to complete

but there is another way to get the result without this search?

@Larryln
but why do you miss
Code: QB64: [Select]
  1. language$(i,2)=language$(j,2)
???
Title: Re: Help with an array
Post by: bplus on April 27, 2020, 06:00:14 pm
j doesn't have to start at 1, it should start at i + 1
Title: Re: Help with an array
Post by: Pete on April 27, 2020, 06:51:17 pm
Quote from: bplus on April 27, 2020, 06:00:14 pm
j doesn't have to start at 1, it should start at i + 1

Good point Mark, provided the user isn't counting the number of times a word is duplicated, only that it is a duplication. Using your i + i logic, the filter is always advancing forward, without needless repetition, again, provided the results are not dependent on the number of occurrences.

Title: Re: Help with an array
Post by: bplus on April 27, 2020, 08:35:42 pm
You know if the j word has already been ID'd as a duplicate...

Oh the array should be sorted first! That would shorten the task considerable!
Title: Re: Help with an array
Post by: SMcNeill on April 27, 2020, 08:43:36 pm
Wouldn't the quick way be to sort the arrays first?  Then it's a case of minimal comparisons -- like so:

LIST 1         LIST 2
Apple           Apple
Bat              Apple
Cat              Bat
Frog            Cat

To start with, you compare list1(0) to list 2(0).   Apple matches Apple.
Then compare to list2(1).  Apple still matches the second Apple.
Then compare to list2(2).  Apple does NOT match Bat.  No need to compare further.

Now, compare list1(1) to list2(2).  Bat matches Bat.
Then compare to list2(3).  Bat doesn't match Cat.  No need to compare further.


Very minimal condition checking is needed once the arrays are sorted.
Title: Re: Help with an array
Post by: STxAxTIC on April 27, 2020, 08:50:48 pm
If you are starting with raw text files with simple formatting, the unix toolkit (grep sed awk etc) can sort and remove duplicates in an instant.
Title: Re: Help with an array
Post by: Pete on April 27, 2020, 09:04:43 pm
Get your own animals, Steve. Stop using mine!

Pete :D
Title: Re: Help with an array
Post by: codeguy on April 28, 2020, 12:51:33 am
I would highly recommend sorting at LEAST one entry list and this way you can use binary search which will cut your accesses to find duplicates by a considerable margin. At most, you'd search 20 times/entry versus an average of 100,000 per entry. You'd cut the required operations from 100,000*200,000 to 20*200,000. A vast improvement. Perhaps my posted sorting library could come in quite handy for this task. 20,000,000,000 versus 4,000,000 operations is a marked improvement. 5,0000 times faster if my mental math isn't off. At 20,0000,000 seek/compare operations, you could age considerably under the proposed solution to search every element in a dimension of the array against elements in other parts of the same array. This would be like seeking the common words of numerous texts for similar words. A thankless task if you try solving it by brute force. The binary search is a powerful weapon.
Title: Re: Help with an array
Post by: bplus on April 28, 2020, 01:13:43 am
Once sorted all the dups would be stacked one upon the other, nothing to search, just count up until the next item appears start another count for it...
Title: Re: Help with an array
Post by: Dimster on April 28, 2020, 11:16:38 am
On trying to find duplicates, I'm not sure how to do that with strings but I have had to figure out how many times a particular value repeats in a given set of data values. Here is the approach I've used with success. Just basically add the your data results as a decimal value to the counter. For example.
Code: QB64: [Select]
  1. Dim Main ( 1 to 20)
  2. Dim Duplicate (1 to 20) ...Rem data 5,20,19,5,18,17 etc
  3. For x = 1 to 20
  4. TargetNum = Main(x)
  5.    For y = 1 to 20
  6.       if Main(y) = TargetNum then Dcount = Dcount  + 1
  7.    Next y
  8.    Duplicate(x) = Dcount + (Main(x) * .01))

The results in the Duplicate are then 1.5, 1.20, 1.19, 2.5, 1.18, 1.17 etc
Any value greater than or equal to 2 is a duplicate
Title: Re: Help with an array
Post by: bplus on April 28, 2020, 01:24:14 pm
Inspired by Qwerkey's B-Day problem https://www.qb64.org/forum/index.php?topic=2514.0

Here is finding duplicate B-days for 100 people assigned a random day:
Code: QB64: [Select]
  1. _TITLE "Duplicate B-Days"
  2.  
  3. DIM SHARED sa$(0 TO 100)
  4. FOR b = 1 TO 100
  5.     sa$(b) = RIGHT$(SPACE$(3) + STR$(INT(RND * (365)) + 1), 3)
  7. QSort 1, 100
  8. PRINT "Duplicates B-Days for 100 people:"
  9. FOR i = 1 TO 100
  10.     count = 0
  11.     PRINT i; ":";
  12.     IF i + 1 > 100 THEN PRINT _TRIM$(STR$(0)): EXIT FOR
  13.     FOR j = i + 1 TO 100
  14.         IF sa$(i) = sa$(j) THEN
  15.             count = count + 1
  16.         ELSE
  17.             PRINT _TRIM$(STR$(count)),
  18.             tDups = tDups + count
  19.             EXIT FOR
  20.         END IF
  21.     NEXT
  22.     i = i + count '<<<<<<<<<<<<<<< skip over what has been counted
  24. PRINT: PRINT "Total Dups:"; tDups
  25.  
  26.  
  27. SUB QSort (Start, Finish) 'sa$ needs to be SHARED  array
  28.     DIM i AS INTEGER, j AS INTEGER, x$, a$
  29.     i = Start
  30.     j = Finish
  31.     x$ = sa$(INT((i + j) / 2))
  32.     WHILE i <= j
  33.         WHILE sa$(i) < x$
  34.             i = i + 1
  35.         WEND
  36.         WHILE sa$(j) > x$
  37.             j = j - 1
  38.         WEND
  39.         IF i <= j THEN
  40.             a$ = sa$(i)
  41.             sa$(i) = sa$(j)
  42.             sa$(j) = a$
  43.             i = i + 1
  44.             j = j - 1
  45.         END IF
  46.     WEND
  47.     IF j > Start THEN QSort Start, j
  48.     IF i < Finish THEN QSort i, Finish
  50.  
  51.  

If the total is 12 that would be like 12%.
Text Only | Text with Attachments