List problem

Hi

The costs for the algorithmen:

-Pauls intersection has O(m+n) (+ Sort: n*log(n)+m*log(m) )

-Stefans $sendall has O(m*n) ( no sort used )

-Rudolfs Algo goes with O(m+n) (+ Sort: (n+m)*log(n+m) )

m,n = #Lines in List 1 and 2

If one List is much bigger than the other, ie. n << m then a Binary Search would be the fastest: O(n*m*log(m)) For a discussion see: articles.leetcode.com/here-is-phone-screening-question-from/

Finding intersection of two sorted arrays – LeetCode<articles.leetcode.com/here-is-phone-screening-question-from/>
articles.leetcode.com
Find the intersection of two sorted arrays. Let’s called array1 as A and array2 as B, each with size m and n. The obvious brute-force solution is to scan through …

Regards,

Udo.

________________________________
Von: omnisdev-en <omnisdev-en-bounces@lists.omnis-dev.com> im Auftrag von Bo Carleö <bo@corbisoft.com>
Gesendet: Montag, 5. Februar 2018 12:26:36
An: OmnisDev List – English
Betreff: Re: List problem

Hi Paul

Interesting comparison!
Did not imagine such a big difference.

My lists are relatively small but I see that it makes big change for large lists.

Regards
Bo

På 5 februari 2018 kl. 11:13:25, Paul Mulroney (pmulroney@logicaldevelopments.com.au) skrev:

Hi Bo,

I did a little performance test, by generating a list of random numbers and then comparing against both routines (our $ListIntersect vs Stephan’s $sendall and $search):

Using List Intersect: 663 ticks
Using $sendall and $search: 1682 ticks.

Re-running produces 645 and 1575 ticks – it’s going to be about the same each time.

Mathematically, I think the $sendall approach is a “N x Log(N)”, whereas the $ListIntersect is a “N” type calculation – as N gets larger the difference between the two is more pronounced.

Regards,
Paul.

##### Method ‘Example2′ #####
No. Local Variable Type Subtype Init.Val/Calc Description
1 i Long integer
2 vlMain List
3 vlResults List
4 vlStates List
5 vnAfter Long integer
6 vnBefore Long integer
7 vnDiff Long integer
8 vnMaxVal Long integer
9 vnValue Long integer
10 voListIntersect Object oListIntersect
11 vsDesc Character 100000000

No. Method text
1 ; Generate large list of random numbers, then find list intersect for smaller list
2
3 Do vlMain.$define(vnValue)
4 Calculate vnMaxVal as pwr(2,32)-1
5 For i from 1 to 65536 step 1
6 Do vlMain.$add(randintrng(1,vnMaxVal))
7 End For
8
9 Do vlCompare.$define(vnValue)
10 For i from 1 to 1000 step 1
11 Do vlCompare.$add(randintrng(1,vnMaxVal))
12 End For
13 Do vlCompare.$cols.vnValue.$removeduplicates(kTrue)
14
15 ; Perform the test
16 Do vlResults.$define(vsDesc,vnDiff)
17 ; – Using List Intersect
18 Calculate vnBefore as #CT
19 Do voListIntersect.$ListIntersect(vlMain,vlCompare,’vnValue’,’Int’)
20 Calculate vnAfter as #CT
21 Calculate vnDiff as vnAfter-vnBefore
22 Do vlResults.$add(‘Using List Intersect: ‘,vnDiff)
23
24 ; – Using Stephan Wuseke’s version from the list
25 Calculate vnBefore as #CT
26 Do vlMain.$sendall($ref.$selected.$assign(kFalse)) ;; $ListIntersect() also deselects list lines
27 Do vlMain.$sendall($ref.$selected.$assign(vlCompare.$search($ref.C1=$sendallref.C1,1,0,0,0)))
28 Calculate vnAfter as #CT
29 Calculate vnDiff as vnAfter-vnBefore
30 Do vlResults.$add(‘Using $sendall and $search: ‘,vnDiff)
31
32 Breakpoint {vlResults}
No method errors found

> Thanks Paul
>
> Problem is solved but I will certainly look into your code.
> Might learn something.
>
> Regards
> Bo
>
> P? 4 februari 2018 kl. 04:50:51, Paul Mulroney (pmulroney@logicaldevelopments.com.au) skrev:
>
> Hi Bo,
>
> I wrote a routine called “ListIntersect”, which I’ve posted on GitHub.
> We originally wrote it in Omnis Studio 3, but it’s up on GitHub in
> Studio 8 format.

I was going to wear my camouflage shirt today, but I couldn’t find it.
—
Paul W. Mulroney We Don’t Do Simple Pty Ltd
pmulroney@logicaldevelopments.com.au Trading as Logical Developments
www.logicaldevelopments.com.au<www.logicaldevelopments.com.au> ACN 161 009 374
Ph: +61 8 9458 3889 86 Coolgardie Street
BENTLEY WA 6102

_____________________________________________________________
Manage your list subscriptions at lists.omnis-dev.com
Start a new message -> mailto:omnisdev-en@lists.omnis-dev.com
_____________________________________________________________
Manage your list subscriptions at lists.omnis-dev.com
Start a new message -> mailto:omnisdev-en@lists.omnis-dev.com
_____________________________________________________________
Manage your list subscriptions at lists.omnis-dev.com
Start a new message -> mailto:omnisdev-en@lists.omnis-dev.com