Op 8/04/2022 om 08:24 schreef Peter J. Holzer:
> On 2022-04-07 17:16:41 +0200, Antoon Pardon wrote:
>> Op 7/04/2022 om 16:08 schreef Joel Goldstick:
>>> On Thu, Apr 7, 2022 at 7:19 AM Antoon Pardon<antoon.pardon@vub.be> wrote:
>>>> I am working with a list of data from which I have to weed out duplicates.
>>>> At the moment I keep for each entry a container with the other entries
>>>> that are still possible duplicates.
> [...]
>> Sorry I wasn't clear. The data contains information about persons. But not
>> all records need to be complete. So a person can occur multiple times in
>> the list, while the records are all different because they are missing
>> different bits.
>>
>> So all records with the same firstname can be duplicates. But if I have
>> a record in which the firstname is missing, it can at that point be
>> a duplicate of all other records.
> There are two problems. The first one is how do you establish identity.
> The second is how do you ween out identical objects. In your first mail
> you only asked about the second, but that's easy.
>
> The first is really hard. Not only may information be missing, no single
> single piece of information is unique or immutable. Two people may have
> the same name (I know about several other "Peter Holzer"s), a single
> person might change their name (when I was younger I went by my middle
> name - how would you know that "Peter Holzer" and "Hansi Holzer" are the
> same person?), they will move (= change their address), change jobs,
> etc. Unless you have a unique immutable identifier that's enforced by
> some authority (like a social security number[1]), I don't think there
> is a chance to do that reliably in a program (although with enough data,
> a heuristic may be good enough).

Yes I know all that. That is why I keep a bucket of possible duplicates
per "identifying" field that is examined and use some heuristics at the
end of all the comparing instead of starting to weed out the duplicates
at the moment something differs.

The problem is, that when an identifying field is judged to be unusable,
the bucket to be associated with it should conceptually contain all other
records (which in this case are the indexes into the population list).
But that will eat a lot of memory. So I want some object that behaves as
if it is a (immutable) list of all these indexes without actually containing
them. A range object almost works, with the only problem it is not
comparable with a list.

--
Antoon Pardon.

On 08/04/2022 08:21, Antoon Pardon wrote:
>
>
> Op 8/04/2022 om 08:24 schreef Peter J. Holzer:
>> On 2022-04-07 17:16:41 +0200, Antoon Pardon wrote:
>>> Op 7/04/2022 om 16:08 schreef Joel Goldstick:
>>>> On Thu, Apr 7, 2022 at 7:19 AM Antoon Pardon<antoon.pardon@vub.be>
>>>> wrote:
>>>>> I am working with a list of data from which I have to weed out
>>>>> duplicates.
>>>>> At the moment I keep for each entry a container with the other entries
>>>>> that are still possible duplicates.
>> [...]
>>> Sorry I wasn't clear. The data contains information about persons.
>>> But not
>>> all records need to be complete. So a person can occur multiple times in
>>> the list, while the records are all different because they are missing
>>> different bits.
>>>
>>> So all records with the same firstname can be duplicates. But if I have
>>> a record in which the firstname is missing, it can at that point be
>>> a duplicate of all other records.
>> There are two problems. The first one is how do you establish identity.
>> The second is how do you ween out identical objects. In your first mail
>> you only asked about the second, but that's easy.
>>
>> The first is really hard. Not only may information be missing, no single
>> single piece of information is unique or immutable. Two people may have
>> the same name (I know about several other "Peter Holzer"s), a single
>> person might change their name (when I was younger I went by my middle
>> name - how would you know that "Peter Holzer" and "Hansi Holzer" are the
>> same person?), they will move (= change their address), change jobs,
>> etc. Unless you have a unique immutable identifier that's enforced by
>> some authority (like a social security number[1]), I don't think there
>> is a chance to do that reliably in a program (although with enough data,
>> a heuristic may be good enough).
>
> Yes I know all that. That is why I keep a bucket of possible duplicates
> per "identifying" field that is examined and use some heuristics at the
> end of all the comparing instead of starting to weed out the duplicates
> at the moment something differs.
>
> The problem is, that when an identifying field is judged to be unusable,
> the bucket to be associated with it should conceptually contain all other
> records (which in this case are the indexes into the population list).
> But that will eat a lot of memory. So I want some object that behaves as
> if it is a (immutable) list of all these indexes without actually
> containing
> them. A range object almost works, with the only problem it is not
> comparable with a list.
>

Is there any reason why you can't use ints? Just set the relevant bits.

Duncan

Op 8/04/2022 om 16:28 schreef duncan smith:
> On 08/04/2022 08:21, Antoon Pardon wrote:
>>
>> Yes I know all that. That is why I keep a bucket of possible duplicates
>> per "identifying" field that is examined and use some heuristics at the
>> end of all the comparing instead of starting to weed out the duplicates
>> at the moment something differs.
>>
>> The problem is, that when an identifying field is judged to be unusable,
>> the bucket to be associated with it should conceptually contain all
>> other
>> records (which in this case are the indexes into the population list).
>> But that will eat a lot of memory. So I want some object that behaves as
>> if it is a (immutable) list of all these indexes without actually
>> containing
>> them. A range object almost works, with the only problem it is not
>> comparable with a list.
>>
>
> Is there any reason why you can't use ints? Just set the relevant bits.

Well my first thought is that a bitset makes it less obvious to calulate
the size of the set or to iterate over its elements. But it is an idea
worth exploring.

--
Antoon.

On 08/04/2022 22:08, Antoon Pardon wrote:
>
> Op 8/04/2022 om 16:28 schreef duncan smith:
>> On 08/04/2022 08:21, Antoon Pardon wrote:
>>>
>>> Yes I know all that. That is why I keep a bucket of possible duplicates
>>> per "identifying" field that is examined and use some heuristics at the
>>> end of all the comparing instead of starting to weed out the duplicates
>>> at the moment something differs.
>>>
>>> The problem is, that when an identifying field is judged to be unusable,
>>> the bucket to be associated with it should conceptually contain all
>>> other
>>> records (which in this case are the indexes into the population list).
>>> But that will eat a lot of memory. So I want some object that behaves as
>>> if it is a (immutable) list of all these indexes without actually
>>> containing
>>> them. A range object almost works, with the only problem it is not
>>> comparable with a list.
>>>
>>
>> Is there any reason why you can't use ints? Just set the relevant bits.
>
> Well my first thought is that a bitset makes it less obvious to calulate
> the size of the set or to iterate over its elements. But it is an idea
> worth exploring.
>

def popcount(n):
"""
Returns the number of set bits in n
"""
cnt = 0
while n:
n &= n - 1
cnt += 1
return cnt

and not tested,

def iterinds(n):
"""
Returns a generator of the indices of the set bits of n
"""
i = 0
while n:
if n & 1:
yield i
n = n >> 1
i += 1

Duncan

Am 08.04.22 um 09:21 schrieb Antoon Pardon:
>> The first is really hard. Not only may information be missing, no single
>> single piece of information is unique or immutable. Two people may have
>> the same name (I know about several other "Peter Holzer"s), a single
>> person might change their name (when I was younger I went by my middle
>> name - how would you know that "Peter Holzer" and "Hansi Holzer" are the
>> same person?), they will move (= change their address), change jobs,
>> etc. Unless you have a unique immutable identifier that's enforced by
>> some authority (like a social security number[1]), I don't think there
>> is a chance to do that reliably in a program (although with enough data,
>> a heuristic may be good enough).
>
> Yes I know all that. That is why I keep a bucket of possible duplicates
> per "identifying" field that is examined and use some heuristics at the
> end of all the comparing instead of starting to weed out the duplicates
> at the moment something differs.
>
> The problem is, that when an identifying field is judged to be unusable,
> the bucket to be associated with it should conceptually contain all other
> records (which in this case are the indexes into the population list).
> But that will eat a lot of memory. So I want some object that behaves as
> if it is a (immutable) list of all these indexes without actually
> containing
> them. A range object almost works, with the only problem it is not
> comparable with a list.

Then write your own comparator function?

Also, if the only case where this actually works is the index of all
other records, then a simple boolean flag "all" vs. "these items in the
index list" would suffice - doesn't it?

Christian

On 09/04/2022 13:14, Christian Gollwitzer wrote:
> Am 08.04.22 um 09:21 schrieb Antoon Pardon:
>>> The first is really hard. Not only may information be missing, no single
>>> single piece of information is unique or immutable. Two people may have
>>> the same name (I know about several other "Peter Holzer"s), a single
>>> person might change their name (when I was younger I went by my middle
>>> name - how would you know that "Peter Holzer" and "Hansi Holzer" are the
>>> same person?), they will move (= change their address), change jobs,
>>> etc. Unless you have a unique immutable identifier that's enforced by
>>> some authority (like a social security number[1]), I don't think there
>>> is a chance to do that reliably in a program (although with enough data,
>>> a heuristic may be good enough).
>>
>> Yes I know all that. That is why I keep a bucket of possible duplicates
>> per "identifying" field that is examined and use some heuristics at the
>> end of all the comparing instead of starting to weed out the duplicates
>> at the moment something differs.
>>
>> The problem is, that when an identifying field is judged to be unusable,
>> the bucket to be associated with it should conceptually contain all other
>> records (which in this case are the indexes into the population list).
>> But that will eat a lot of memory. So I want some object that behaves as
>> if it is a (immutable) list of all these indexes without actually
>> containing
>> them. A range object almost works, with the only problem it is not
>> comparable with a list.
>
>
> Then write your own comparator function?
>
> Also, if the only case where this actually works is the index of all
> other records, then a simple boolean flag "all" vs. "these items in the
> index list" would suffice - doesn't it?
>
>     Christian
>
Writing a comparator function is only possible for a given key. So my
approach would be:

1) Write a comparator function that takes params X and Y, such that:
if key data is missing from X, return 1
If key data is missing from Y return -1
if X > Y return 1
if X < Y return -1
return 0 # They are equal and key data for both is present

2) Sort the data using the comparator function.

3) Run through the data with a trailing enumeration loop, merging
matching records together.

4) If there are no records copied out with missing
key data, then you are done, so exit.

5) Choose a new key and repeat from step 1).

Regards

Ian

--
Ian Hobson
Tel (+66) 626 544 695

--
This email has been checked for viruses by AVG.
https://www.avg.com

Op 9/04/2022 om 02:01 schreef duncan smith:
> On 08/04/2022 22:08, Antoon Pardon wrote:
>>
>> Well my first thought is that a bitset makes it less obvious to calulate
>> the size of the set or to iterate over its elements. But it is an idea
>> worth exploring.
>>
>
>
>
> def popcount(n):
>     """
>     Returns the number of set bits in n
>     """
>     cnt = 0
>     while n:
>         n &= n - 1
>         cnt += 1
>     return cnt
>
> and not tested,
>
> def iterinds(n):
>     """
>     Returns a generator of the indices of the set bits of n
>     """
>     i = 0
>     while n:
>         if n & 1:
>             yield i
>         n = n >> 1
>         i += 1
>
Sure but these seem rather naive implementation with a time complexity of
O(n) where n is the maximum number of possible elements. Using these would
turn my O(n) algorithm in a O(n^2) algorithm.

--
Antoon Pardon.

On 10/04/2022 21:20, Antoon Pardon wrote:
>
>
> Op 9/04/2022 om 02:01 schreef duncan smith:
>> On 08/04/2022 22:08, Antoon Pardon wrote:
>>>
>>> Well my first thought is that a bitset makes it less obvious to calulate
>>> the size of the set or to iterate over its elements. But it is an idea
>>> worth exploring.
>>>
>>
>>
>>
>> def popcount(n):
>>     """
>>     Returns the number of set bits in n
>>     """
>>     cnt = 0
>>     while n:
>>         n &= n - 1
>>         cnt += 1
>>     return cnt
>>
>> and not tested,
>>
>> def iterinds(n):
>>     """
>>     Returns a generator of the indices of the set bits of n
>>     """
>>     i = 0
>>     while n:
>>         if n & 1:
>>             yield i
>>         n = n >> 1
>>         i += 1
>>
> Sure but these seem rather naive implementation with a time complexity of
> O(n) where n is the maximum number of possible elements. Using these would
> turn my O(n) algorithm in a O(n^2) algorithm.
>

I thought your main concern was memory. Of course, dependent on various
factors, you might be able to do much better than the above. But I don't
know what your O(n) algorithm is, how using a bitset would make it
O(n^2), or if the O(n^2) algorithm would actually be slower for typical
n. The overall thing sounds broadly like some of the blocking and
clustering methods I've come across in record linkage.

Duncan

On 2022-04-10 at 22:20:33 +0200,
Antoon Pardon <antoon.pardon@vub.be> wrote:

>
>
> Op 9/04/2022 om 02:01 schreef duncan smith:
> > On 08/04/2022 22:08, Antoon Pardon wrote:
> > >
> > > Well my first thought is that a bitset makes it less obvious to calulate
> > > the size of the set or to iterate over its elements. But it is an idea
> > > worth exploring.
> > >
> >
> >
> >
> > def popcount(n):
> >     """
> >     Returns the number of set bits in n
> >     """
> >     cnt = 0
> >     while n:
> >         n &= n - 1
> >         cnt += 1
> >     return cnt
> >
> > and not tested,
> >
> > def iterinds(n):
> >     """
> >     Returns a generator of the indices of the set bits of n
> >     """
> >     i = 0
> >     while n:
> >         if n & 1:
> >             yield i
> >         n = n >> 1
> >         i += 1
> >
> Sure but these seem rather naive implementation with a time complexity of
> O(n) where n is the maximum number of possible elements. Using these would
> turn my O(n) algorithm in a O(n^2) algorithm.

O(n) where n is the expected number of elements. The loops iterate once
for each bit actually contained in the set, which is usually [much] less
than the size of the universe. If you have lots and lots of elements in
your sets, or your universe is large and n is a long integer, then these
may not be as efficient as other methods. You know your data better
than we do.

Op 11/04/2022 om 02:01 schreef duncan smith:
> On 10/04/2022 21:20, Antoon Pardon wrote:
>>
>>
>> Op 9/04/2022 om 02:01 schreef duncan smith:
>>> On 08/04/2022 22:08, Antoon Pardon wrote:
>>>>
>>>> Well my first thought is that a bitset makes it less obvious to
>>>> calulate
>>>> the size of the set or to iterate over its elements. But it is an idea
>>>> worth exploring.
>>>>
>>>
>>>
>>>
>>> def popcount(n):
>>>     """
>>>     Returns the number of set bits in n
>>>     """
>>>     cnt = 0
>>>     while n:
>>>         n &= n - 1
>>>         cnt += 1
>>>     return cnt
>>>
>>> and not tested,
>>>
>>> def iterinds(n):
>>>     """
>>>     Returns a generator of the indices of the set bits of n
>>>     """
>>>     i = 0
>>>     while n:
>>>         if n & 1:
>>>             yield i
>>>         n = n >> 1
>>>         i += 1
>>>
>> Sure but these seem rather naive implementation with a time
>> complexity of
>> O(n) where n is the maximum number of possible elements. Using these
>> would
>> turn my O(n) algorithm in a O(n^2) algorithm.
>>
>
> I thought your main concern was memory. Of course, dependent on
> various factors, you might be able to do much better than the above.
> But I don't know what your O(n) algorithm is, how using a bitset would
> make it O(n^2), or if the O(n^2) algorithm would actually be slower
> for typical n. The overall thing sounds broadly like some of the
> blocking and clustering methods I've come across in record linkage.

Using bitsets would make change my algorithm from O(n) into O(n^2) because
the bitset operations are O(n) instead of O(1). If I have a 20000 people
a bitset will take a vector of about 300, 64bit words. With 40000 people
the bitset will take a vector of about 600. So doubling the population
will also double the time for the bitset operations, meaning doubling
the population will increase execution time four times.