Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #78164 > unrolled thread
| Started by | LJ <luisjosenovoa@gmail.com> |
|---|---|
| First post | 2014-09-22 09:57 -0700 |
| Last post | 2014-09-23 21:13 +1000 |
| Articles | 5 — 3 participants |
Back to article view | Back to comp.lang.python
Comparison LJ <luisjosenovoa@gmail.com> - 2014-09-22 09:57 -0700
Re: Comparison Chris Angelico <rosuav@gmail.com> - 2014-09-23 03:11 +1000
Re: Comparison LJ <luisjosenovoa@gmail.com> - 2014-09-22 10:38 -0700
Re: Comparison Chris Angelico <rosuav@gmail.com> - 2014-09-23 03:45 +1000
Re: Comparison Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-09-23 21:13 +1000
| From | LJ <luisjosenovoa@gmail.com> |
|---|---|
| Date | 2014-09-22 09:57 -0700 |
| Subject | Comparison |
| Message-ID | <521ef86a-df52-4a49-8562-6312273a8c07@googlegroups.com> |
Hi All, Quick question here. In the code I am working on I am apparently doing a lot of dictionary lookups and those are taking a lot of time. I looked at the possibility of changing the structure and I found about the numpy structured arrays. The concrete question is: what would be the difference between using one or the other in terms of performance? meaning looping and performing checks an operations on them? Thanks,
[toc] | [next] | [standalone]
| From | Chris Angelico <rosuav@gmail.com> |
|---|---|
| Date | 2014-09-23 03:11 +1000 |
| Message-ID | <mailman.14223.1411405879.18130.python-list@python.org> |
| In reply to | #78164 |
On Tue, Sep 23, 2014 at 2:57 AM, LJ <luisjosenovoa@gmail.com> wrote: > Quick question here. In the code I am working on I am apparently doing a lot of dictionary lookups and those are taking a lot of time. > I looked at the possibility of changing the structure and I found about the numpy structured arrays. > The concrete question is: what would be the difference between using one or the other in terms of performance? meaning looping and performing checks an operations on them? The lookups themselves almost certainly aren't actually taking the time, unless you have some kind of crazy hash collision happening, which is so statistically unlikely that it would have to have come from malice. What's the code doing? What are you trying to accomplish? It's much more likely that you have an algorithmic flaw than a data type inefficiency. ChrisA
[toc] | [prev] | [next] | [standalone]
| From | LJ <luisjosenovoa@gmail.com> |
|---|---|
| Date | 2014-09-22 10:38 -0700 |
| Message-ID | <0be2cb54-4520-4379-a9bb-279cfe134d19@googlegroups.com> |
| In reply to | #78168 |
On Monday, September 22, 2014 1:12:23 PM UTC-4, Chris Angelico wrote: > On Tue, Sep 23, 2014 at 2:57 AM, LJ <luisjosenovoa@gmail.com> wrote: > > > Quick question here. In the code I am working on I am apparently doing a lot of dictionary lookups and those are taking a lot of time. > > > I looked at the possibility of changing the structure and I found about the numpy structured arrays. > > > The concrete question is: what would be the difference between using one or the other in terms of performance? meaning looping and performing checks an operations on them? > > > > The lookups themselves almost certainly aren't actually taking the > > time, unless you have some kind of crazy hash collision happening, > > which is so statistically unlikely that it would have to have come > > from malice. What's the code doing? What are you trying to accomplish? > > It's much more likely that you have an algorithmic flaw than a data > > type inefficiency. > > > > ChrisA Thank you for your reply. Basically what is happening is the following: I have a network in which the nodes are defined as dictionaries using the NetworkX package. Inside each node (each dictionary) I defined a dictionary of dictionaries holding attributes corresponding to different ways in which the node can be reached (this dictionaries I refer to as labels). At some point in my algorithm I am looping through some subset of nodes and through the labels in each node and I perform some "joining" checks with the labels of each node in another subset of nodes. To clarify I check for a feasibility condition in a pairwise manner for every label in one node and every label of another. This nested loop is taking time. I wonder if the fact of defining the labels using numpy instead of dictionaries could imply a faster way to perform this loop. I hope I was clear. Thanks.
[toc] | [prev] | [next] | [standalone]
| From | Chris Angelico <rosuav@gmail.com> |
|---|---|
| Date | 2014-09-23 03:45 +1000 |
| Message-ID | <mailman.14224.1411407926.18130.python-list@python.org> |
| In reply to | #78169 |
On Tue, Sep 23, 2014 at 3:38 AM, LJ <luisjosenovoa@gmail.com> wrote: > At some point in my algorithm I am looping through some subset of nodes and through the labels in each node and I perform some "joining" checks with the labels of each node in another subset of nodes. To clarify I check for a feasibility condition in a pairwise manner for every label in one node and every label of another. This nested loop is taking time. > Okay, that's where the issue is - you're doing a cross-match, that's going to be comparing every label against every other. You might be able to cache some references to part-way into the tree, depending on how your code is written, but ultimately, you still need to do all of those checks. What's the definition of feasibility? Can you optimize that? Maybe there's a way to do a rough check that cuts down the number you have to do the exact check on. ChrisA
[toc] | [prev] | [next] | [standalone]
| From | Steven D'Aprano <steve+comp.lang.python@pearwood.info> |
|---|---|
| Date | 2014-09-23 21:13 +1000 |
| Message-ID | <542155cd$0$6599$c3e8da3$5496439d@news.astraweb.com> |
| In reply to | #78169 |
LJ wrote:
> I have a network in which the nodes are defined as dictionaries using the
> NetworkX package. Inside each node (each dictionary) I defined a
> dictionary of dictionaries holding attributes corresponding to different
> ways in which the node can be reached (this dictionaries I refer to as
> labels). At some point in my algorithm I am looping through some subset of
> nodes and through the labels in each node and I perform some "joining"
> checks with the labels of each node in another subset of nodes. To clarify
> I check for a feasibility condition in a pairwise manner for every label
> in one node and every label of another. This nested loop is taking time. I
> wonder if the fact of defining the labels using numpy instead of
> dictionaries could imply a faster way to perform this loop.
I doubt it very much. Python dicts are extremely fast, and it doesn't sound
like your problem is that each dict lookup is slow. It sounds like your
problem is that you are doing a lot of them.
If you have 100 labels in one node, and 100 labels in the other, and you are
doing:
for label_a in A:
for label_b in B:
is_feasible(label_a, label_b)
the total number of feasibility checks is 100*100 = 10000, not the 200 that
you may be expecting. The bottleneck here is probably your is_feasible
check, called many times, not the dict look-ups.
But of course we cannot be sure without seeing your code, and we can't be
certain without running the profiler and seeing exactly where your
bottlenecks are.
--
Steven
[toc] | [prev] | [standalone]
Back to top | Article view | comp.lang.python
csiph-web