Help with an array

[Larryrl]

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.

[Pete]

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
19. NEXT i
20. ' PRINT concat$
21. seed = 1
22. DO
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)
45. NEXT
46. PRINT
47. PRINT "[Unique Words]"
48. FOR i = 1 TO cnt2
49.     PRINT edup$(i)
50. NEXT

[Larryrl]

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)
9. next j
10. wend
11.  
12.  

[Pete]

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

[TempodiBasic]

@Pete

yes, math is not an opinion

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)

???

[bplus]

j doesn't have to start at 1, it should start at i + 1

[Pete]

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.

[bplus]

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!

[SMcNeill]

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.

[STxAxTIC]

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.

[Pete]

Get your own animals, Steve. Stop using mine!

Pete :D

[codeguy]

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.

[bplus]

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...

[Dimster]

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))
9. Next x

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

[bplus]

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)
6. NEXT
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
23. NEXT
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
49. END SUB
50.  
51.  

If the total is 12 that would be like 12%.