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