I understand, hash-table(unordered_map in c++) is the only data structures
that beats the tree representation in c++, there's drawbacks though, as you
mentioned, and one more drawback is that you can't really sort the
polynomial using this data structure, cause it's a "1-1" function, the only
way to do that is by sorting the pairs from the beginning, which require
O(nlogn) computational time.Note that in the tree representation i can
traverse the tree in inorder fashion and return it sorted so there's no
need for further functions.
Yes, i compared it to other data structures like arrays(list in python) and
linked lists which is the most common way to represent polynomials.
If the user gives the coefficients and exponents ordered, let's say [
{1,3}, {3,2}, {1,1} ] which is P(x) = X^3 + 3X^2 + X, then the list wins
as we just have to push_back(O(1) time complexity) the pairs.But, if i want
to add more and more pairs as i continue, lets say i want to add {2, 5}
which is 2X^5 to my polynomial, then i can't just push back the pair, cause
i will lose the order. So in this case, the AVL tree wins.In order to have
a sorted polynomial with a linked list i must have O(n) insertion time
complexity.
Now if you use lists in python, let's say i want to represent a polynomial
P(x) = X^1000 + X, then i'll need max(exponent(P)) slots in my list.But
with an AVL tree i'll just need 2 nodes.
I understand what is happening in python, that's why intense testing is
needed.Because something in theory seems faster does not mean that's always
the case.
Spiros.
Στις Τετάρτη 17 Ιανουαρίου 2024 στις 9:29:47 μ.μ. UTC+2, ο χρήστης Oscar
έγραψε:
> On Wed, 17 Jan 2024 at 15:54, Spiros Maggioros <maggior...@gmail.com>
> wrote:
>
>> So we showed that, using AVL trees instead of arrays is much better(note
>> that even linked lists is slower cause the insertion time complexity is
>> O(n)).
>>
>
> Interesting. Did you compare the AVL tree with other sparse data
> structures?
>
>
>> I have not seen the data structure that is used in SymPy, but i'm
>> planning to check what i need to see cause right now i'm in exam period and
>> i have no time at all.
>>
>
> No problem. If you want to learn more about how these things are
> implemented in SymPy then I recommend starting by learning how to use the
> lower-level data structures. This doc page is a little out of date since
> (as of current master) SymPy can make use of python-flint in some places
> but it shows how to access things:
>
> https://docs.sympy.org/latest/modules/polys/domainsintro.html
>
> The DUP representation is what you describe as an "array" (a "list" in
> Python terminology). The DMP representation uses this recursively for
> multivariate polynomials. Sparse polynomials are implemented using
> hash-tables (dicts). The doc page I just linked explains how to create and
> introspect these data structures and how they are used within SymPy.
>
> The situation in Python is a bit different from C or other languages with
> lower interpreter overhead because the downsides of using say a hash-table
> vs an array are much lower in a relative sense. This is a quick and dirty
> measurement of the time to lookup an item in a dict vs a list using ipython:
>
> In [28]: hashtable = dict(zip(range(100000), range(1, 100000+1)))
>
> In [29]: array = list(range(100000))
>
> In [30]: %timeit hashtable[1000]
> 56.2 ns ± 1.03 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops
> each)
>
> In [31]: %timeit array[1000]
> 22.2 ns ± 0.12 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops
> each)
>
> In C the difference in lookup time between a hash-table and an array would
> be much more than 2.5x (an array lookup would be more like 1ns). The reason
> they are not so different in Python is because there is so much interpreter
> overhead in both cases that the real underlying operation does not
> really take a majority of the runtime. I think that probably tends to shift
> what data structures seem fastest in the context of SymPy when compared to
> implementations of the same operations in other languages.
>
> --
> Oscar
>
--
You received this message because you are subscribed to the Google Groups
"sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sympy+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/sympy/9241cfb0-0a25-4d30-8bbf-08c7656e2199n%40googlegroups.com.
