473,699 Members | 2,804 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

algorithm for "common array of longs"

Hi

I have a number of arrays of longs, from which I need to find a single
array which only contains the values which appear in all the original
arrays.

For example, I could have the three arrays:

1, 3, 2, 8, 5
3, 6, 1
6, 1, 4, 3

from which I need to generate the "common" array:
1, 3
(as these are the only values which appear in all the original arrays).
What is a good algorithm for this? The below is what I have written,
which does seem to do what I want. But more than likely there is a much
better, more efficient way to do this...

static void Main(string[] args)
{
long[] x = new long[5] { 1, 3, 2, 8, 5 };
long[] y = new long[3] { 3, 6, 1 };
long[] z = new long[4] { 6, 1, 4, 3 };

List<long[]originals = new List<long[]{ x, y, x };

long[] commonArray = Common(original s);
}

static long[] Common(List<lon g[]originals)
{
long[] temp = originals[0];

for (int i = 1; i < originals.Count ; i++)
{
temp = Common(temp, originals[i]);
}

return temp;
}

static long[] Common(long[] one, long[] two)
{
List<longcommon = new List<long>();
foreach (long val in one)
{
if (two.Contains(v al))
{
common.Add(val) ;
}
}
return common.ToArray( );
}
Thanks,
Peter
Oct 1 '08 #1
6 1740
If the lists are large and sorted, a double walk over the 'index' in
parallel can be implemented. If the list are short and not sorted, the list
can be walked through, kind of what you did, rather than first sorted and
next using a index walk in parallel, because the time spent to sort them may
be more than what you will win by using the double walk on the 'index'. That
is why SQL has execution plan based on statistics: given different cases,
the 'imperative code' used will be different. There is also a question of
memory: can you use a lot or are you limited to the strict minimum? Anyhow,
here how a walk on index in parallel works (note that it is what SQL can
perform to execute an INNER JOIN between two lists with no dup).

0. R is an empty list,
FingerA points to before the start of the listA
FingerB points to before the start of the listB
1. Finger A points the next item in list A, itemA
2. If fingerA points to nothing, it is done.
3. Find next item in listB equals to itemA
3a. If none is found, goto 1
4. Append itemA to R
5. Move FingerB to the next item in listB, itemB
6. If fingerB points to nothing, it is done.
7. Find next item in listA equals to itemB
7a. If none if found, goto 5
8. Append itemB to R
9 Goto 1.
note that you can change lightly the algorithm if listB has duplicated
values (I assumed both list have not dup), but I don't think this is the
kind of JOIN you want.

Example: listA: 1, 2, 3, 5, 8
list B: 1, 5, 6

Step 1: fa -1
Step 3: fb-1, R =={ 1 }
Step 5: fb-5
Step 7: fa-5, R =={ 1, 5 }
Step 1: fa->8
Step 3a.
Step 1: fa-eof
so, R={ 1, 5 }

Now, for the code... I would use SQL, but feel free to do it in C# though
:-)

Vanderghast, Access MVP

"Peter" <xd****@hotmail .comwrote in message
news:OX******** ******@TK2MSFTN GP06.phx.gbl...
Hi

I have a number of arrays of longs, from which I need to find a single
array which only contains the values which appear in all the original
arrays.

For example, I could have the three arrays:

1, 3, 2, 8, 5
3, 6, 1
6, 1, 4, 3

from which I need to generate the "common" array:
1, 3
(as these are the only values which appear in all the original arrays).
What is a good algorithm for this? The below is what I have written,
which does seem to do what I want. But more than likely there is a much
better, more efficient way to do this...

static void Main(string[] args)
{
long[] x = new long[5] { 1, 3, 2, 8, 5 };
long[] y = new long[3] { 3, 6, 1 };
long[] z = new long[4] { 6, 1, 4, 3 };

List<long[]originals = new List<long[]{ x, y, x };

long[] commonArray = Common(original s);
}

static long[] Common(List<lon g[]originals)
{
long[] temp = originals[0];

for (int i = 1; i < originals.Count ; i++)
{
temp = Common(temp, originals[i]);
}

return temp;
}

static long[] Common(long[] one, long[] two)
{
List<longcommon = new List<long>();
foreach (long val in one)
{
if (two.Contains(v al))
{
common.Add(val) ;
}
}
return common.ToArray( );
}
Thanks,
Peter
Oct 1 '08 #2
Peter wrote:
Hi

I have a number of arrays of longs, from which I need to find a single
array which only contains the values which appear in all the original
arrays.

For example, I could have the three arrays:

1, 3, 2, 8, 5
3, 6, 1
6, 1, 4, 3

from which I need to generate the "common" array:
You need the intersection of different sets. Intersect the first with
the second and the result with the third. There are plenty of
algorithms to do that. I have a few (relying on the sets of numbers
being sorted), but they are unfortunately not in C#.

A quick translation (may be faulty) - note that the lists must be
sorted for this to work - it is generally much faster than calling
Contains() in a loop:

public static int SetIntersection <T>(IList<Tsour ce1,
IList<Tsource2, IList<Tdestinat ion, IComparer<Tcomp arer)
{
int i1 = 0;
int i2 = 0;
int d = 0;
while (i1 < source1.Count && i2 < source2.Count)
{
int comp = comparer.Compar e(source1[i1], source2[i2]);
if (comp < 0)
i1++;
else if (comp 0)
i2++;
else
{
destination[d] = source1[i1];
i1++;
i2++;
d++;
}
}
return d;
}

Of course destination must be big enough to contain the largest of the
source lists entirely.

if list1, list2 and list3 are the 3 lists, then do

int len = SetIntersection <int>(list1, list2, intermediate,
Comparer<int>.D efault);
intermediate.De leteRange(len, intermediate.Co unt - len);
len = SetIntersection <int>(intermedi ate, list3, result,
Comparer<int>.D efault);
result.DeleteRa nge(len, result.Count - len);

And result will contain the elements present in all. You could modify
the routine to pass d back as well, so you know the number of items
written to it.
--
Rudy Velthuis http://rvelthuis.de

"We are not retreating - we are advancing in another Direction."
-- General Douglas MacArthur (1880-1964)
Oct 1 '08 #3
Peter wrote:
Hi

I have a number of arrays of longs, from which I need to find a single
array which only contains the values which appear in all the original
arrays.

For example, I could have the three arrays:

1, 3, 2, 8, 5
3, 6, 1
6, 1, 4, 3

from which I need to generate the "common" array:
1, 3
(as these are the only values which appear in all the original arrays).
What is a good algorithm for this? The below is what I have written,
which does seem to do what I want. But more than likely there is a much
better, more efficient way to do this...

static void Main(string[] args)
{
long[] x = new long[5] { 1, 3, 2, 8, 5 };
long[] y = new long[3] { 3, 6, 1 };
long[] z = new long[4] { 6, 1, 4, 3 };

List<long[]originals = new List<long[]{ x, y, x };

long[] commonArray = Common(original s);
}

static long[] Common(List<lon g[]originals)
{
long[] temp = originals[0];

for (int i = 1; i < originals.Count ; i++)
{
temp = Common(temp, originals[i]);
}

return temp;
}

static long[] Common(long[] one, long[] two)
{
List<longcommon = new List<long>();
foreach (long val in one)
{
if (two.Contains(v al))
{
common.Add(val) ;
}
}
return common.ToArray( );
}
Thanks,
Peter
The Contains method for a List gets slower the larger the list is, a
HashSet scales much better:

static long[] Common(long[] one, long[] two) {
HashSet<longset = new HashSet<long>(t wo);
List<longcommon = new List<long>();
foreach (long val in one) {
if (set.Contains(v al)) common.Add(val) ;
}
return common.ToArray( );
}

--
Göran Andersson
_____
http://www.guffa.com
Oct 1 '08 #4
Seems much more compact that the pseudo code I tried to used...and working
fine. I would use destination.Add ( source1[i1] ) instead of
destination[d]=source1[i1], though.

I wonder what LINQ.Intesect uses?

Int[] first = { 1, 3, 2, 8, 5};
Int[] second = { 6, 1, 4, 3};
IEnumerable<int common = first.Intersect (second);
Vanderghast, Access MVP

"Rudy Velthuis" <ne********@rve lthuis.dewrote in message
news:xn******** ******@news.mic rosoft.com...
Peter wrote:
>Hi

I have a number of arrays of longs, from which I need to find a single
array which only contains the values which appear in all the original
arrays.

For example, I could have the three arrays:

1, 3, 2, 8, 5
3, 6, 1
6, 1, 4, 3

from which I need to generate the "common" array:

You need the intersection of different sets. Intersect the first with
the second and the result with the third. There are plenty of
algorithms to do that. I have a few (relying on the sets of numbers
being sorted), but they are unfortunately not in C#.

A quick translation (may be faulty) - note that the lists must be
sorted for this to work - it is generally much faster than calling
Contains() in a loop:

public static int SetIntersection <T>(IList<Tsour ce1,
IList<Tsource2, IList<Tdestinat ion, IComparer<Tcomp arer)
{
int i1 = 0;
int i2 = 0;
int d = 0;
while (i1 < source1.Count && i2 < source2.Count)
{
int comp = comparer.Compar e(source1[i1], source2[i2]);
if (comp < 0)
i1++;
else if (comp 0)
i2++;
else
{
destination[d] = source1[i1];
i1++;
i2++;
d++;
}
}
return d;
}

Of course destination must be big enough to contain the largest of the
source lists entirely.

if list1, list2 and list3 are the 3 lists, then do

int len = SetIntersection <int>(list1, list2, intermediate,
Comparer<int>.D efault);
intermediate.De leteRange(len, intermediate.Co unt - len);
len = SetIntersection <int>(intermedi ate, list3, result,
Comparer<int>.D efault);
result.DeleteRa nge(len, result.Count - len);

And result will contain the elements present in all. You could modify
the routine to pass d back as well, so you know the number of items
written to it.
--
Rudy Velthuis http://rvelthuis.de

"We are not retreating - we are advancing in another Direction."
-- General Douglas MacArthur (1880-1964)
Oct 1 '08 #5
Michel Walsh wrote:
Seems much more compact that the pseudo code I tried to used...and
working fine. I would use destination.Add ( source1[i1] ) instead of
destination[d]=source1[i1], though.
I designed mine to work with arrays too.
I wonder what LINQ.Intesect uses?

Int[] first = { 1, 3, 2, 8, 5};
Int[] second = { 6, 1, 4, 3};
IEnumerable<int common = first.Intersect (second);
I translated that from a language without LINQ. <g>

I guess LINQ would be a lot easier.
--
Rudy Velthuis http://rvelthuis.de

"Our children are not born to hate, they are raised to hate."
-- Thomas della Peruta
Oct 1 '08 #6
Göran Andersson brought next idea :
Peter wrote:
>Hi

I have a number of arrays of longs, from which I need to find a single
array which only contains the values which appear in all the original
arrays.

For example, I could have the three arrays:

1, 3, 2, 8, 5
3, 6, 1
6, 1, 4, 3

from which I need to generate the "common" array:
1, 3
(as these are the only values which appear in all the original arrays).
What is a good algorithm for this? The below is what I have written,
which does seem to do what I want. But more than likely there is a much
better, more efficient way to do this...

static void Main(string[] args)
{
long[] x = new long[5] { 1, 3, 2, 8, 5 };
long[] y = new long[3] { 3, 6, 1 };
long[] z = new long[4] { 6, 1, 4, 3 };

List<long[]originals = new List<long[]{ x, y, x };

long[] commonArray = Common(original s);
}

static long[] Common(List<lon g[]originals)
{
long[] temp = originals[0];

for (int i = 1; i < originals.Count ; i++)
{
temp = Common(temp, originals[i]);
}

return temp;
}

static long[] Common(long[] one, long[] two)
{
List<longcommon = new List<long>();
foreach (long val in one)
{
if (two.Contains(v al))
{
common.Add(val) ;
}
}
return common.ToArray( );
}
Thanks,
Peter

The Contains method for a List gets slower the larger the list is, a HashSet
scales much better:

static long[] Common(long[] one, long[] two) {
HashSet<longset = new HashSet<long>(t wo);
List<longcommon = new List<long>();
foreach (long val in one) {
if (set.Contains(v al)) common.Add(val) ;
}
return common.ToArray( );
}
If you are using HashSets, why not:

long[] x = new long[5] { 1, 3, 2, 8, 5 };
long[] y = new long[3] { 3, 6, 1 };
long[] z = new long[4] { 6, 1, 4, 3 };

HashSet<longhs1 = new HashSet<long>(x );
hs1.IntersectWi th(y);
hs1.IntersectWi th(z);

foreach(var l in hs1)
Console.WriteLi ne(l);
(returns 1 and 3)

Hans Kesting
Oct 2 '08 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

7
2208
by: Arnaud | last post by:
Hi, I work with php 4.3.4 and I don't understand the way php sort this array for example : <? $array = (-1, 30, "test", true); sort($array); var_dump($array); ?>
7
5071
by: Sherry Littletree | last post by:
Hi All I am working on a site that has a large amount of common html on all its web pages. I am looking for a way to place this in a single file so, if changes are made, I can change this single file and do not have to change each and every page. I have the Java scripting in a common .Js file but have not been able to find a way to do this with my html content.
6
2113
by: sonic | last post by:
what exactly is the difference ? I think that is more suitable for declarative arrays, but not exactly sure why. TIA
4
7604
by: Greg Stark | last post by:
I find myself wishing I had a syntax "LIKE ANY (array)". I don't see much value in the = ANY, = ALL, <> ANY, <> ALL syntax since they're equivalent more or less to IN and NOT IN. But it could be neat if other operators were supported. As it turns out this isn't immediately relevant, it will only be relevant when one day the database drivers use the binary FE protocol and support binding arrays directly. Then I could pass an...
0
1841
by: Klemens | last post by:
what do entry's like this in db2diag.log indicate? ------------------------------------------- 2004-01-14-09.07.52.650000 Instance:WWS Node:000 PID:3512(db2syscs.exe) TID:1116 Appid:*LOCAL.WWS.01AFC9110326 data protection sqlpALR_OpenExtent Probe:5 Database:XTRADE RenameArray: add unarchived log 1227. 2004-01-14-09.07.52.947000 Instance:WWS Node:000 PID:3512(db2syscs.exe) TID:1116 Appid:*LOCAL.WWS.01AFC9110326
2
2126
by: Simon Morgan | last post by:
I hope this isn't OT, I looked for a newsgroup dealing purely with algorithms but none were to be found and seeing as I'm trying to implement this in C I thought this would be the best place. I have an array of structs containing data which I'd like to output ordered based on the value of a single member. I was wondering if there is a relatively simple way of doing this without actually modifying the structure of the array? I had a...
3
14498
by: Pablo Gutierrez | last post by:
I have a C# method that reads Binary data (BLOB type) from a database and returns the data an array of bytes (i.e byte outbyte = new byte;). The BLOB column is saved into the database by a C program (UNIX) as an array of "struct point" where struct point //C structure { int Time; //32 bits
5
3206
by: Jim Carlock | last post by:
I've set up the following using an Alias in Apache... Alias /phpdocs/ "C:/Apache/htdocs/common/docs/php/" <Directory "C:/Apache/htdocs/common/docs/php"> Options Indexes FollowSymlinks MultiViews AllowOverride None Order allow,deny Allow from all </Directory>
30
2937
by: josh | last post by:
Hi all, what does it meaning that strange sintax (look at the object :) ? if I have i.e. array.length I can use array. and is it IE/Firefox compatible??
0
8615
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
9174
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
8883
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
7750
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
6534
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5874
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
4629
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
3057
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
3
2009
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.