On 22/09/2021 22:28, Ilya Maximets wrote:
> On 9/21/21 12:33, Mark Gray wrote:
>> On 17/09/2021 18:17, Ilya Maximets wrote:
>>> Current algorithm for ovsdb_datum_subtract looks like this:
>>>
>>> for-each atom in a:
>>> if atom in b:
>>> swap(atom, )
>>> destroy(atom)
On 9/22/21 23:28, Ilya Maximets wrote:
> On 9/21/21 12:33, Mark Gray wrote:
>> On 17/09/2021 18:17, Ilya Maximets wrote:
>>> Current algorithm for ovsdb_datum_subtract looks like this:
>>>
>>> for-each atom in a:
>>> if atom in b:
>>> swap(atom, )
>>> destroy(atom)
>>>
On 9/21/21 12:33, Mark Gray wrote:
> On 17/09/2021 18:17, Ilya Maximets wrote:
>> Current algorithm for ovsdb_datum_subtract looks like this:
>>
>> for-each atom in a:
>> if atom in b:
>> swap(atom, )
>> destroy(atom)
>> quicksort(a)
>>
>> Complexity:
>>
>> Na *
On 17/09/2021 18:17, Ilya Maximets wrote:
> Current algorithm for ovsdb_datum_subtract looks like this:
>
> for-each atom in a:
> if atom in b:
> swap(atom, )
> destroy(atom)
> quicksort(a)
>
> Complexity:
>
> Na * log2(Nb) + (Na - Nb) * log2(Na - Nb)
>
Current algorithm for ovsdb_datum_subtract looks like this:
for-each atom in a:
if atom in b:
swap(atom, )
destroy(atom)
quicksort(a)
Complexity:
Na * log2(Nb) + (Na - Nb) * log2(Na - Nb)
Search Comparisons for quicksort
It's not optimal,