Month: May 2019
Curious Effects Getting List Extents
I have a program that gets a list of GPS waypoints, and wants to figure out their bounding box. The naive way[1] to do this is find the maximum and minimum latitude and longitude, and use the maxes as one corner and the minimums as the other corner.
Off the top of my head, I can think of two ways to do this: Iterate the list of waypoints, comparing to the max and minimum so far, and updating as I go. The list has N points, I have to look at all of them, so O(N), so far so good.
The other way to do it is to do list comprehensions to get the latitudes and longitudes as separate lists, and then call max() and min() on each of those. I would assume that each list comprehension is O(N), and each call to max() or min() is also O(N), since they have to look through the whole list to find the maximum or minimum, and so it is 6 loops over the list (2 comprehensions, 2 max() calls, 2 min() calls), and so this is the slower way to do it.
It turns out, not so much.
I ran the code below on Repl.it and got, usually, the list comprehension version being just very slightly faster to twice as fast. Occasionally, the 10,000 instance case is slower, but not all the time.
import random
from timeit import default_timer as timer
#Try some different sizes of lists
for jj in [10, 100, 1000, 10000, 100000, 1000000]:
#Set up N waypoints
waypoints = []
for ii in range(jj):
lat = (random.random() * 360) - 180
lon = (random.random() * 360) - 180
waypoints.append({"lat":lat, "lon":lon})
start = timer()
# One loop
maxLat = maxLon = -float("inf")
minLat = minLon = float("inf")
for point in waypoints:
lat = float(point["lat"])
if lat < minLat:
minLat = lat
if lat > maxLat:
maxLat = lat
lon = float(point["lon"])
if lon < minLon:
minLon = lon
if lon > maxLon:
maxLon = lon
mid = timer()
# List comprehensions
lons = [float(point["lon"]) for point in waypoints]
lats = [float(point["lat"]) for point in waypoints]
minLat1 = min(lats)
minLon1 = min(lons)
maxLat1 = max(lats)
maxLon1 = max(lons)
end = timer()
#Print the results
print(f"{jj} points")
print(f" first way {mid-start}")
print(f" second way {end-mid}")
print(f" speedup {(mid-start)/(end-mid)}")
assert(minLat == minLat1)
assert(maxLat == maxLat1)
assert(minLon == minLon1)
assert(maxLon == maxLon1)
So why is it faster? Clearly, I’m assuming something wrong. I suspect the main thing that I’m assuming wrong is that the constant 6 multiplied by the O(N) matters. It probably doesn’t, and that’s why we typically drop the constant multipliers in runtime comparisons. It’s likely that list comprehensions and max()/min() of iterables are calls to a very fast C implementation, and are just so much faster than my loop in Python that the fact that I’m doing 6 iterations doesn’t really matter.
Another thing that I’m assuming is that max and min are implemented as linear searches over iterables. It’s entirely possible that iterables store references to their maximum and minimum values, and just return that when asked, rather than going looking. I doubt it, since the overhead on removing an element would be large [2], but it is possible.
I haven’t looked into either of these assumptions, since timing the runs answered the question I had (“Which is faster?”), and the follow-on question (“Why?”) isn’t useful to me at this time.
[1] It does some stupid stuff around the poles and across the international date line, for example.
[2] You’ve removed the largest element. What is the new largest? Time to go searching…
Alternatively, the list could be implemented as a parallely-linked-list, where one set of links is the elements in their list order, and the other set is the elements in their sorted order, but then the list [1, 3, 5, “pickles”, <built-in method foo of Bar object at 0x1f34b881>, 6] doesn’t have well-defined links for the sorted order.
Drag and Drop Python Objects in WxPython
I’m working on a UI for a system that has agents, which have some qualities, and units, which have multiple agents. I want to be able to display each unit as a list, and drag agents from that list to other units, to reassign them.
There are a lot of examples for using drag and drop with text and files, because WxPython provides drop targets for text and files already. One way that this could be implemented is to serialize the dragged objects to JSON, drop them as text, and then de-serialize them. This has some disadvantages, notably that you end up restricted by what you can pass via JSON. I wanted to pass Python objects, so I used pickle.
What I eventually came up with is below. It uses ObjectListView, which is a great wrapper around WxPython’s ListCtrl. On drag, the selected items of the source list are pickled and passed through the Wx drag and drop mechanism. When they are dropped on another ObjectListView, they are then unpickled and added to that ObjectListView (OLV), and removed from the source OLV.
One thing that this code does leave up to the programmer is ensuring that what goes in on one side of the drag and drop is the same as what is expected out on the other side. Another, slightly more subtle thing, is that this uses pickle on the drop data, so it would be possible to have a script that generates malicious pickle data, and lets you drag it from another UI window to my script’s OLV, whereupon it unpickles into something nasty.
That said, if your attacker is sitting at your computer, launching malicious programs and dragging and dropping stuff out of them, you have already lost, and should probably invest in better door locks.
#!/usr/bin/env python
import wx
import pickle
from ObjectListView import ObjectListView, ColumnDefn #pip install objectlistview
import wx.lib.scrolledpanel as scrolled
# UI with a few list boxes that can be drag/dropped between, and have title bars
class Agent(object):
# Model of a single agent, has:
# identifier (string?)
# range (km)
# speed (kph)
# capacity (integer)
def __init__(self, ident, range, speed, capacity):
self.ident = ident
self.range = range
self.speed = speed
self.capacity = capacity
def __repr__(self):
return f"<Agent: {self.ident}>"
# Drag and drop Drop target that supports receiving pickled
# python data structures and doing something with them.
class GenericDropTarget(wx.DropTarget):
def __init__(self, object):
super(GenericDropTarget, self).__init__()
self.object = object
self.data = wx.CustomDataObject("PickleData")
self.SetDataObject(self.data)
def OnData(self, x, y, defResult):
#print(f"OnData({x},{y})")
if self.GetData():
# unpickle data and do something with it
pickled_stuff = self.data.GetData()
cukes = pickle.loads(pickled_stuff)
# TODO We are making the assumption that a "PickleData"
# actually only has a list of Agents in it.
# Add some checking before making this a real thing, or
# limit the type to a more-specific format like "AgentList"
self.object.AddObjects(cukes)
return defResult
def OnDrop(self, x, y):
#print(f"OnDrop({x},{y})")
return True
def OnDragOver(self, x, y, defResult):
#print(f"OnDragOver({x},{y})")
return defResult
def OnEnter(self, x, y, defResult):
#print(f"OnEnter({x},{y})")
return defResult
class UnitPanel(wx.Panel):
def __init__(self, parent, unitName="No name set"):
wx.Panel.__init__(self, parent=parent, id=wx.ID_ANY)
self.dataOlv = ObjectListView(self, wx.ID_ANY, style=wx.LC_REPORT|wx.SUNKEN_BORDER)
self.dataOlv.SetColumns([
ColumnDefn("ID", "left", -1, "ident", minimumWidth=100),
ColumnDefn("Range", "right", -1, "range", minimumWidth=60),
ColumnDefn("Speed", "right", -1, "speed", minimumWidth=60),
ColumnDefn("Capacity", "right", -1, "capacity", minimumWidth=60)
])
self.agents = []
self.dataOlv.SetObjects(self.agents)
self.dataOlv.Bind(wx.EVT_LIST_BEGIN_DRAG, self.OnDragInit)
# Set up a drop target on the listview
dt = GenericDropTarget(self.dataOlv)
self.dataOlv.SetDropTarget(dt)
# Set up a title for this box
self.unitLabel = wx.StaticText(self, id=wx.ID_ANY, label=unitName)
mainSizer = wx.BoxSizer(wx.VERTICAL)
mainSizer.Add(self.unitLabel, proportion=0, flag=wx.ALL, border=5)
mainSizer.Add(self.dataOlv, proportion=1, flag=wx.ALL|wx.EXPAND, border=5)
self.SetSizer(mainSizer)
def populate(self, units):
self.agents = []
# for unit in units:
# self.agents.append(Agent(unit["ident"], unit["range"], unit["speed"], unit["capacity"]))
# self.dataOlv.SetObjects(self.agents)
for unit in units:
a = Agent(unit["ident"], unit["range"], unit["speed"], unit["capacity"])
self.dataOlv.AddObject(a)
#self.draggableURLText.Bind(wx.EVT_MOTION, self.OnStartDrag)
def OnDragInit(self, event):
# Get all the selected items from this list
selected = self.dataOlv.GetSelectedObjects()
# Pickle them and put them in a custom data object
pickled_selection = pickle.dumps(selected)
drag_obj = wx.CustomDataObject("PickleData")
drag_obj.SetData(pickled_selection)
#Create a drag and drop source from this ObjectListView
src = wx.DropSource(self.dataOlv)
src.SetData(drag_obj)
print("Drag started")
result = src.DoDragDrop(wx.Drag_DefaultMove)
if result == wx.DragCopy:
# We don't copy because agents are hardware
self.dataOlv.RemoveObjects(selected)
elif result == wx.DragMove:
# Remove the data from here, add it to another list
self.dataOlv.RemoveObjects(selected)
else:
# Default, do nothing
print("Nothing, nothing, nothing at all")
class AssetFrame(wx.Frame):
def __init__(self):
wx.Frame.__init__(self, parent=None, id=wx.ID_ANY,
title="ObjectListView Demo", size=(800, 600))
self.panel = scrolled.ScrolledPanel(self, id=wx.ID_ANY)
self.mainSizer = wx.BoxSizer(wx.VERTICAL)
self.panel.SetSizer(self.mainSizer)
self.panel.SetupScrolling()
self.Show()
def populate(self, config):
for unit in config["units"]:
unit_panel = UnitPanel(self.panel, unitName=unit["name"])
unit_panel.populate(unit["agents"])
self.mainSizer.Add(unit_panel)
if __name__ == "__main__":
app = wx.App(False)
# We're going to need to be able to populate the frame from the config,
# so represent the data as a data structure and initialze with that
config = {"units": [{"name": "Unimatrix 01",
"agents": [
{"ident": "7 of 9", "range": 10, "speed": 10, "capacity": 12},
{"ident": "Third of 5", "range": 10, "speed": 10, "capacity": 12}
]},
{"name": "Unit 2",
"agents": [
{"ident": "u2s1", "range": 10, "speed": 10, "capacity": 12},
{"ident": "u2a2", "range": 10, "speed": 10, "capacity": 12},
{"ident": "u2a3", "range": 10, "speed": 10, "capacity": 12}
]},
{"name": "Unit Foo",
"agents": [
{"ident": "bar", "range": 10, "speed": 10, "capacity": 12},
{"ident": "baz", "range": 10, "speed": 10, "capacity": 12},
{"ident": "quux", "range": 10, "speed": 10, "capacity": 12}
]},
{"name": "Enterprise",
"agents": [
{"ident": "Galileo", "range": 10, "speed": 10, "capacity": 12},
{"ident": "Copernicus", "range": 10, "speed": 10, "capacity": 12}
]},
{"name": "GSV Insufficent Gravitas",
"agents": [
{"ident": "GCU Nervous Energy", "range": 1000000, "speed": 3452334, "capacity": 13452342},
{"ident": "GCU Grey Area", "range": 1000000, "speed": 234523546, "capacity": 234562312}
]}]
}
frame = AssetFrame()
frame.populate(config)
app.MainLoop()
I called the unpickled data “cukes” because this is demo code, and I was being silly. A cucumber is, after all, what you get when you undo the process of making pickles. You may want to change that if you copy/paste this into production code.
Recent Comments