Best way to compare two lists
phani
I am looking for a way to compare(equal or not) two lists with large
elements. What is the efficient way for doing this?
I want to avoid comparing item by item for performance reasons. I
tried with [regexp $list1 $list2] but it returns true(1) even if one
list is subset of the other. This doesn't help me because i want to
check whether both are exactly equal or not.
Is there a way to achieve this using regexp or any better way?
Thanks for the help,
Phani
Gerry Snyder
> Hi All,
>
> I am looking for a way to compare(equal or not) two lists with large
> elements. What is the efficient way for doing this?
> I want to avoid comparing item by item for performance reasons. I
> tried with [regexp $list1 $list2] but it returns true(1) even if one
> list is subset of the other.
How about:
[expr {$list1 eq $list2}]
?
Harald Oehlmann
> On 9/13/2010 3:46 PM, phani wrote:
> > I am looking for a way to compare(equal or not) two lists with large
> > elements. What is the efficient way for doing this?
I would love to have native "list is equal" somewhere...
Here is an older thread on this and its impacts:
http://groups.google.com/group/comp.lang.tcl/browse_thread/thread/be2e59c2b4ca454e/5b76e8f2f44bf90b
If you do the upper, be shure to have "canonical lists", e.g. they are
composed by a list command.
If not shure, do:
[expr {[lrange $l1 0 end] eq [lrange $l2 0 end]}]
Lawrence Woodman
Phani,
When you were using regexp your were telling it to look for $list1 in
$list2 so of course when $list1 was a subset of $list2 it returned true,
notice that it wouldn't have done so if you had reversed the parameters.
Try using:
if {$list1 eq $list2} {
# The two lists are equal
...
} else {
# The two lists are not equal
...
}
Lorry
Arjen Markus
This solution and the others all construct a string representation of
both
lists. If the lists are indeed composed of large elements (I
interpreted that
as meaning: long strings or long sublists), then this may by itself
impose
a performance penalty.
Have you measured whether element-by-element comparison is too slow?
For instance:
proc listsEqual (list1 list2) {
if { [llength $list1] != [llength $list2] } {
return 0
} else {
foreach el1 $list1 el2 $list2 {
if { $el1 ne $el2 } {
return 0
}
}
return 1
}
}
is the fastest I can think of right now.
The optimisations are:
- The lists must be of equal length
- The elements are converted to strings one by one only
- Use "ne" to compare strings rather than attempt numerical
comparison
first
- Put the code in proc, so that you can be sure it is byte-compiled
(Global code used not to be compiled - I am not sure if that is
still
the case in Tcl 8.5 and later)
Regards,
Arjen
Jonathan Bromley
> This solution and the others all construct a
> string representation of both lists.
Indeed; but Arjen's solution may also do the same thing,
in a smaller way, if the list's elements have non-string
internal representation (list, dict, ...), because it
uses "eq" to compare the elements.
Does the "eq" operator always shimmer to string before
comparing, or is it somehow polymorphic? I assume the
former. So I don't see how you can avoid the risk of
shimmering somewhere in the comparison.
In the absence of some way to divine the internal
representation of a variable, I'm at a loss to see
how to avoid this unless you know the details of
the list's structure. You can't even use llength==1
as a check for "is it a simple string", because
the single element might itself be a list.
--
Jonathan Bromley
Arjen Markus
wrote:
Hm, you are right - if the lists are equal, then all elements
will have to be tranformed to strings for ne to work. The
main advantage with my code is that the string conversion
does not take place in one round - so if the lists are not
equal, then it pays off ;).
I happen to have heard a rumour that it is possible to
divine the nature of a Tcl_Obj value from within the
script level ... but that is an unsupported feature of 8.6
Regards,
Arjen
Alexandre Ferrieux
>
> I happen to have heard a rumour that it is possible to
> divine the nature of a Tcl_Obj value from within the
> script level ... but that is an unsupported feature of 8.6
Now please everybody look at the red light in the device I'm
holding...
-Alex
Helmut Giese
>holding...
Arjen Markus
They are, just as the Tcl Illuminati.
There are NO Tcl Illuminati.
Regards,
Arjen
Don Porter
> Does the "eq" operator always shimmer to string before
> comparing, or is it somehow polymorphic? I assume the
> former. So I don't see how you can avoid the risk of
> shimmering somewhere in the comparison.
String rep generation != shimmering.
--
| Don Porter Mathematical and Computational Sciences Division |
| donald...@nist.gov Information Technology Laboratory |
| http://math.nist.gov/~DPorter/ NIST |
|______________________________________________________________________|
Jonathan Bromley
> String rep generation != shimmering.
OK, so I need educating: I thought shimmering was
precisely the automatic conversion of one internal
representation into another, as required by the
current operation. Can someone put me straight?
thanks
--
Jonathan Bromley
Uwe Klein
more like repeatedly loosing the validity of
the "other" representation form.
# just a string:
set num 0
# just an integer:
# set num [expr 0]
while true {
incr num ;# convert to integer rep, increment by "1"
append num 0 ;# convert to string rep, append character "0"
}
Alexandre Ferrieux
wrote:
Yes but the string rep is not one of the internal reps. Both can
coexist.
As to you previous question on the two equality operators:
(1) "eq" (mapping to the INST_STR_EQ bytecode instruction) explicitly
computes the string reps and compares them, unless the objects are
identical (same pointer).
(2) "==" (mapping to the INST_EQ bytecode instruction) first tries to
shimmer to numbers, and if that fails for either operand, does as
"eq".
How do I know ? Just read tclExecute.c ;-)
-Alex
Jonathan Bromley
> the string rep is not one of the internal reps. Both can
> coexist.
Ah, that makes perfect sense. Thanks.
> How do I know ? Just read tclExecute.c ;-)
Unfair! I want to go on being just a stupid user
who writes scripts...
--
Jonathan Bromley
Don Porter
> Unfair! I want to go on being just a stupid user
> who writes scripts...
That's fine, but in that case hold back on your impulses to explain
Tcl's internals in public.
phani
> On 9/13/2010 3:46 PM, phani wrote:
>
Thanks you all,
Phani
Jonathan Bromley
> > Unfair! I want to go on being just a stupid user
> > who writes scripts...
> That's fine, but in that case hold back on your impulses to explain
> Tcl's internals in public.
Actually I think that may be a tad unfair too. I correctly
described an issue that might cause unexpected performance
problems; I used the wrong terminology to describe it, and
was happy to be corrected. But I reserve the right to try
to learn about, and to try to discuss, Tcl internals when
they impact my scripting in a visible way, even if visible
only in terms of performance.
Forming mental models of how a tool works is an important
part of the learning process for that tool (or language,
or whatever). Sometimes those models will be flawed, and
will give rise to demonstrably incorrect theorizing about
what's going on. In that case, refutation is welcome and
appropriate. Scientific method, or something like that.
I also reserve the right to put my tongue in my cheek...
and I reserve the right to be grateful for the excellent
general quality of discussion and information here.
--
Jonathan Bromley