This is valid code, and does what you expect:
list_ = [ 'A', 'B', 'C' ]
print list_[False] # 'A'
print list_[True] # 'B'
... which is neat, but it upsets me a little bit. You index into things with integers, not floats, not strings, and certainly not bools. This smells more like Javascript than Python. If I want to use a bool to index values out I can do that with a dict.
I'm reworking the web server for my irrigation project. I've already got "kr", which restarts a program whenever it detects the source files have been updated, but first I need the existing web service to close down when there is a change to the source code. For this I implemented the code below, which defines a class. Calling an instance of the class will check the loaded modules (with custom filtering available) for changes to their source code. If a change is found, a callback is made. You can shut down your web server with the callback. The only tricky part is getting the event loop to periodically call the check function. It worked fine for my architecture that doesn't block indefinitely. Later I'll probably add an option for having a background thread do the monitoring.
The file is available on github here.
#!python
#Copyright 2015 Mark Santesson
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
# Test with: kr.py *.py -c watch_modules.py
import os
import re
import sys
class ImportedModulesTimestampChecker(object):
'''
A class to help detect when one of the source files for a
running process has changed.
The returned object should be called periodically to let it check
the timestamps of all files. There is, as of yet, no multi-threaded
version.
Typical use of this module would be to have it track the files
being actively developed and to call a function resulting in program
exit (perhaps sys.exit) when a change is detected. This works well
when combined with "kr" to relaunch the program.
'''
def __init__(self, on_difference_fn, filename_filter_fn=None):
'''
Takes two parameters:
on_difference_fn: a function taking the name of the file which
changed, which is called when the change is
detected.
filename_filter_fn: a function taking a module's filename and
which should return True if the file's timestamp
should be observed. If the filename filter is a
string, then any filenames containing that string
will be observed. If not present, then all modules
will be tracked.
'''
self._onDifferenceFn = on_difference_fn
if isinstance(filename_filter_fn, basestring):
filename_filter_fn = lambda x: filename_filter_fn in x
self._filenameFilterFn = filename_filter_fn or (lambda x:True)
self._timestamps = {}
def __call__(self):
'''
Call this periodically to do a check of the timestamps.
'''
# Get the timestamps on all matching files in this module's
# directory. If any have changed, quit.
all_files = [ x.__file__ for x in sys.modules.values()
if isinstance(x,type(sys))
and hasattr(x, '__file__')
and self._filenameFilterFn(x.__file__)
]
for module_name in sorted(all_files):
module_name = re.sub(r'\.pyc$', r'.py', module_name)
try:
ts = os.stat(module_name).st_mtime
except WindowsError: # TODO: What is the error on Linux?
logging.exception(module_name)
pass
else:
if ts > self._timestamps.setdefault(module_name, ts):
self._onDifferenceFn(module_name)
self._timestamps[module_name] = ts
def main():
import os.path
import SocketServer
import logging
# From an example in the documentation for SocketServer.
class TinyHandler(SocketServer.StreamRequestHandler):
def handle(self):
# Get one line.
self.data = self.rfile.readline().strip()
logging.info('Received: %r', self.data)
out = self.data.lower()
self.wfile.write(out)
logging.info('Sending : %r', out)
class TinySocketServer(SocketServer.TCPServer):
def __init__(self):
self._address = ("localhost", 9999)
SocketServer.TCPServer.__init__( self
, self._address
, TinyHandler )
self.timeout = 0.5
self.quit = False
self._timestampChecker = ImportedModulesTimestampChecker\
( self.on_module_modification
, self.module_name_filter
)
@staticmethod
def module_name_filter(module_name):
this_mod_name = os.path.basename(__file__).split('.')[0]
return this_mod_name in module_name
def on_module_modification(self, module_name):
logging.info('Module %s was modified, exiting.', module_name)
self.quit = True
def run(self):
logging.info('Listening at: %s', self._address)
while not self.quit:
self._timestampChecker()
self.handle_request()
logging.info('Quitting.')
logging.getLogger().setLevel(20)
tws = TinySocketServer()
tws.run()
if __name__ == "__main__":
main()
I used to work at Pipeworks Software. We did really cool things like the original XBox demos. I didn't work on Desk Toys, but I did most all of the Ping Pong Ball and Mousetrap room. I did the butterfly flight in Butterfly Garden. I also did part of the boot screen that was used for the original generation XBox. I did the fog, camera paths, and blobby goo.
For Godzilla: Destroy All Monsters Melee" I worked on special effects, rigid body physics, &c. At one point I was coding the results of a monster being thrown into a building. Whenever you destroy a building it is supposed to make the people a bit more angry at you. Unfortunately, when a monster was thrown into a building we had no record of who threw the monster into it. As I contemplated how much work would need to be done to track that information I realized that I could just attribute the destruction to the monster that was thrown. After all, if someone throws me onto an ant pile, the ants are going to get mad at me.
I walked over to a designer and ran the idea past him. It would let the player force some human anger onto their opponent. This wasn't a big deal, but could affect the game as the humans would attack the monster that was doing the most damage to their city. Humans could never kill you, but they could take you down to about 10% health through machine gun fire from helicopters. It seemed like the change would work okay, so I went back and implemented it.
That saved me a few minutes of time and some added complexity to the data structures. And I thought it was a nice feature.
I just added a page to the blog introducing my major side project. I've built an Arduino based flow sensor that monitors my irrigation water usage. (It also keeps an eye on my automatic pool filler.) It mails me graphs of water usage every morning so that I can easily see if a sprinkler head has been broken off, thereby saving me money and worry. It also emails me if flow stays on for longer than a set time (in case I've forgotten to turn off water filling the pool). I can check the flow rate in real time from a web page.
I haven't yet packaged up the source, but I'll do that soon. Check it out and leave me comments.
I've been working on learning Django. There's probably a better way of doing this that I don't know about, but as near as I can tell there is no way to back up the state of the db in any way that can migrate across versions. There is
There is a stack overflow question on the topic here. It is an old question, with a few third party solutions. A more recent answer references new Django support for migrations. However, migrations requires that you write significant code for non-trivial changes.
I wanted a solution that would let my classes load themselves from older representations. Preferably automatically, but with the option of custom code for non-trivial cases. I searched around a while and could not find anything, so I wrote it myself.
An example project that illustrates using xmldump is here. The only file you need to use it yourself is serializable.py which defines a mixin. Include it as a base class for any models that you want to be able to dump to xml. The file also includes documentation on how to use it, which I've include that below.
The serializable module can save django data to xml format and
reimport. The intent is that in most cases no customization should
be required. However, I expect that there are still many cases where
the code is not yet able to handle the model relationships.
For instance, I have made no particular effort to implement many to
many relationships.
To generate xml from the models currently in memory:
import serializable
xml = serializable.models_to_xml([TopLevelModelClass1, Class2])
The xml that is returned is an instance of the xml.etree.ElmentTree.Element
class. To display it in a readable format:
from xml.dom.minidom import parseString
doc = parseString( xml.etree.ElmentTree.tostring(xml) )
xml_string = doc.toprettyxml(' ')
In order to delete all the data in memory (in preparation for reloading it,
presumably):
delete_all_models_in_db([TopLevelModelClass1, Class2])
The list of class names that must be passed to the functions need not
contain all the model classes. They should contain the highest level
classes only. The module will discover contained classes, whether they
be models which are referred to by a foreign key, or models which refer
to the high level model class through a foreign key.
However, it may be advisable to overload the "owned_models" function
in order to restrict the default discovery. In some cases it makes
for a nicer xml nesting if references are not followed all the way
down.
<?xml version="1.0" ?>
<ModelData>
<xmldump.models.Menu>
<id type="int">1</id>
<name type="unicode">Breakfast</name>
<___owned>
<xmldump.models.MenuItem>
<menu to_type="xmldump.models.Menu" type="reference">1</menu>
<price type="float">4.0</price>
<id type="int">1</id>
<name type="unicode">Spam and Eggs</name>
</xmldump.models.MenuItem>
<xmldump.models.MenuItem>
<menu to_type="xmldump.models.Menu" type="reference">1</menu>
<price type="float">4.5</price>
<id type="int">2</id>
<name type="unicode">Eggs and Spam</name>
</xmldump.models.MenuItem>
<xmldump.models.MenuItem>
<menu to_type="xmldump.models.Menu" type="reference">1</menu>
<price type="float">5.0</price>
<id type="int">3</id>
<name type="unicode">Spammity Spam</name>
</xmldump.models.MenuItem>
<xmldump.models.MenuItem>
<menu to_type="xmldump.models.Menu" type="reference">1</menu>
<price type="float">3.0</price>
<id type="int">4</id>
<name type="unicode">Spam</name>
</xmldump.models.MenuItem>
</___owned>
</xmldump.models.Menu>
<xmldump.models.Order>
<customer type="unicode">Brian</customer>
<date type="date">2015-03-04</date>
<id type="int">1</id>
<___owned>
<xmldump.models.OrderEntry>
<order to_type="xmldump.models.Order" type="reference">1</order>
<count type="int">1</count>
<menuitem to_type="xmldump.models.MenuItem" type="reference">1</menuitem>
<id type="int">1</id>
</xmldump.models.OrderEntry>
<xmldump.models.OrderEntry>
<order to_type="xmldump.models.Order" type="reference">1</order>
<count type="int">1</count>
<menuitem to_type="xmldump.models.MenuItem" type="reference">2</menuitem>
<id type="int">2</id>
</xmldump.models.OrderEntry>
<xmldump.models.OrderEntry>
<order to_type="xmldump.models.Order" type="reference">1</order>
<count type="int">2</count>
<menuitem to_type="xmldump.models.MenuItem" type="reference">4</menuitem>
<id type="int">3</id>
</xmldump.models.OrderEntry>
</___owned>
</xmldump.models.Order>
</ModelData>
(Thanks to Free Online XML Escape Tool - freeformatter.com.)
Python has a great class for storing and manipulating the date and time: datetime.
Unfortunately, it is not the only way to refer to a point in time. Sometimes you need to convert between the two and I frequently forget how to do it.
Here is a table of conversions. Pick the row corresponding to the form of time that you have (from the left), and them pick the column corresponding to the form that you would like (from the top). The intersecting cell is the code snippet to get you there.
I have some measure of confidence in the correctness since the table, indeed, this entire post, was created by a script which tested the code shown in the table and lists below. That script is available here. However, I expect that many of the conversions can be improved upon and many may be subtly, or not so subtly, incorrect. Please let me know if you have an improvement.
I'm sorry, but this table just isn't going to work on mobile. Below is a breakout by the type of representation that you are converting to.
|
To
Timezone Naive Datetime Local |
To
Timezone Naive Datetime UTC |
To
Timezone Aware Datetime |
To
Time Struct Local |
To
Time Struct UTC |
To
Timestamp |
|
|---|---|---|---|---|---|---|
| Build as of now | datetime . now ( ) | datetime . utcnow ( ) | localtz . localize ( datetime . now ( ) ) . astimezone ( othertz ) | time . localtime ( ) | time . gmtime ( ) | time . time ( ) |
|
From
Timezone Naive Datetime Local |
localtz . localize ( dt ) . astimezone ( pytz . utc ) . replace ( tzinfo = None ) | localtz . localize ( dt ) . astimezone ( othertz ) | dt . timetuple ( ) | localtz . localize ( dt ) . utctimetuple ( ) | time . mktime ( dt . timetuple ( ) ) + 1e-6 * dt . microsecond | |
|
From
Timezone Naive Datetime UTC |
pytz . utc . localize ( dt ) . astimezone ( localtz ) . replace ( tzinfo = None ) | pytz . utc . localize ( dt ) . astimezone ( othertz ) | pytz . utc . localize ( dt ) . astimezone ( localtz ) . timetuple ( ) | dt . utctimetuple ( ) | calendar . timegm ( pytz . utc . localize ( dt ) . timetuple ( ) ) + 1e-6 * dt . microsecond | |
|
From
Timezone Aware Datetime |
dt . astimezone ( localtz ) . replace ( tzinfo = None ) | dt . astimezone ( pytz . utc ) . replace ( tzinfo = None ) | dt . astimezone ( localtz ) . timetuple ( ) | dt . utctimetuple ( ) | calendar . timegm ( dt . utctimetuple ( ) ) + 1e-6 * dt . microsecond | |
|
From
Time Struct Local |
datetime ( *t[:6] ) | datetime . utcfromtimestamp ( time . mktime ( t ) ) | localtz . localize ( datetime ( *t[:6] ) ) . astimezone ( othertz ) | time . gmtime ( time . mktime ( t ) ) | time . mktime ( t ) | |
|
From
Time Struct UTC |
pytz . utc . localize ( datetime ( *t[:6] ) ) . astimezone ( localtz ) . replace ( tzinfo = None ) | datetime . utcfromtimestamp ( calendar . timegm ( t ) ) | pytz . utc . localize ( datetime ( *t[:6] ) ) . astimezone ( othertz ) | time . localtime ( calendar . timegm ( t ) ) | calendar . timegm ( t ) | |
|
From
Timestamp |
datetime . fromtimestamp ( secs ) | datetime . utcfromtimestamp ( secs ) | localtz . localize ( datetime . fromtimestamp ( secs ) ) | time . localtime ( secs ) | time . gmtime ( secs ) |
| From | To Timezone Naive Datetime Local |
|---|---|
| Timezone Naive Datetime UTC | pytz.utc.localize(dt).astimezone(localtz).replace(tzinfo=None) |
| Timezone Aware Datetime | dt.astimezone(localtz).replace(tzinfo=None) |
| Time Struct Local | datetime(*t[:6]) |
| Time Struct UTC | pytz.utc.localize(datetime(*t[:6])).astimezone(localtz).replace(tzinfo=None) |
| Timestamp | datetime.fromtimestamp(secs) |
To build as of now: datetime.now()
| From | To Timezone Naive Datetime UTC |
|---|---|
| Timezone Naive Datetime Local | localtz.localize(dt).astimezone(pytz.utc).replace(tzinfo=None) |
| Timezone Aware Datetime | dt.astimezone(pytz.utc).replace(tzinfo=None) |
| Time Struct Local | datetime.utcfromtimestamp(time.mktime(t)) |
| Time Struct UTC | datetime.utcfromtimestamp(calendar.timegm(t)) |
| Timestamp | datetime.utcfromtimestamp(secs) |
To build as of now: datetime.utcnow()
| From | To Timezone Aware Datetime |
|---|---|
| Timezone Naive Datetime Local | localtz.localize(dt).astimezone(othertz) |
| Timezone Naive Datetime UTC | pytz.utc.localize(dt).astimezone(othertz) |
| Time Struct Local | localtz.localize(datetime(*t[:6])).astimezone(othertz) |
| Time Struct UTC | pytz.utc.localize(datetime(*t[:6])).astimezone(othertz) |
| Timestamp | localtz.localize(datetime.fromtimestamp(secs)) |
To build as of now: localtz.localize(datetime.now()).astimezone(othertz)
| From | To Time Struct Local |
|---|---|
| Timezone Naive Datetime Local | dt.timetuple() |
| Timezone Naive Datetime UTC | pytz.utc.localize(dt).astimezone(localtz).timetuple() |
| Timezone Aware Datetime | dt.astimezone(localtz).timetuple() |
| Time Struct UTC | time.localtime(calendar.timegm(t)) |
| Timestamp | time.localtime(secs) |
To build as of now: time.localtime()
| From | To Time Struct UTC |
|---|---|
| Timezone Naive Datetime Local | localtz.localize(dt).utctimetuple() |
| Timezone Naive Datetime UTC | dt.utctimetuple() |
| Timezone Aware Datetime | dt.utctimetuple() |
| Time Struct Local | time.gmtime(time.mktime(t)) |
| Timestamp | time.gmtime(secs) |
To build as of now: time.gmtime()
| From | To Timestamp |
|---|---|
| Timezone Naive Datetime Local | time.mktime(dt.timetuple())+1e-6*dt.microsecond |
| Timezone Naive Datetime UTC | calendar.timegm(pytz.utc.localize(dt).timetuple())+1e-6*dt.microsecond |
| Timezone Aware Datetime | calendar.timegm(dt.utctimetuple())+1e-6*dt.microsecond |
| Time Struct Local | time.mktime(t) |
| Time Struct UTC | calendar.timegm(t) |
To build as of now: time.time()
import pytz, datetime
pytz.timezone('UTC').localize(datetime.utcnow())
pytz.timezone('US/Central').localize(datetime.now())
print 'Common timezones:',pytz.common_timezones
0 4 * * * (rm /tmp/scan ; ((clamscan -i -l /tmp/scan -z --exclude-dir="^/(dev|cdrom|media/cdrom|sys)" -r /)) ; chmod a+r /tmp/scan ; ( cd /home/myusr/dir_with_password ; su -c "python /home/myusr/lib/cp_email.py --ob run-and-send @password @password recipient@email.com cat /tmp/scan --subject='Antivirus'" myusr))
0 4 * * * ( cd /home/usrofsvn/markets/Code/irrigate ; python ../lib/cp_email.py --ob run-and-send @password @password recipient@email.com clamscan -r / --subject="Antivirus run")
Whether developing on my desktop or laptop, Linux or Windows, my tools of choice are pretty bare-bones. I edit my files in vim and I incrementally develop my program by using my "kr" script. "kr" looks for changes in whatever files you give it, and then reruns a command when it detects a change. I.e.:
> kr *.py -c 'tests.py'
Would look for a change in any .py file and rerun the "tests.py" script.
> kr *.c *.h makefile -c 'make ; application param1 param2'
Would look for a change in any .c/.h file, or the makefile, and when a change is detected it remakes and runs "application" with the two params "param1" and "param2".
Developing is easy, just save the file I'm editing and look in the other window to see what happens with the new code. Usually I use this for re-running a python program, which I develop a bit at a time. I fix an error, save, and quickly see the next error. It works best, of course, when the file is able to run quickly.
I've also used it to check for a data file change, at which point it regenerates an image. In another window a separate "kr" script looks for a change in the image file, and runs a program to render it. (The two "kr" scripts had to run on different machines, or else they could have been combined.)
#Copyright 2012 Mark Santesson
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
import sys
import time
import re
import stat
import os
import glob
import operator
import optparse
if __name__ == "__main__":
parser = optparse.OptionParser (
usage = '%prog -c files ...',
description = 'Repeatedly run a command whenever any one of a list of files changes.')
parser.add_option('-c', '--command', dest='command', type="string",
help='Specify command to run when a change is detected')
options, args = parser.parse_args()
# print "Found args: " + repr(args)
# print "Found command: " + repr(options.command)
if not args:
print '\n' + os.path.basename( sys.argv[0] ) + ' requires some files to monitor.'
sys.exit(1)
if not options.command:
print '\nError: A command to run is required.'
sys.exit(1)
file_times = dict()
globbed = sum( [ glob.glob(x) for x in args ], [] )
for x in globbed:
file_times[x] = 0.0
print file_times
while True:
rerun = False
for f in file_times.keys():
attempts_left = 5
t = None
while attempts_left and t == None:
try:
t = os.stat(f)[ stat.ST_MTIME ]
except WindowsError, e:
time.sleep(0.1)
attempts_left -= 1
if t > file_times[f]:
rerun = True
file_times[f] = t
if rerun:
print time.strftime('\n\n--- Rerunning at %H:%M:%S :') + repr(options.command)
ret = os.system( options.command )
if ret:
print '\n\n--- ERRORED %r' % (ret,) + time.strftime(' at %H:%M:%S.')
else:
print time.strftime('\n\n--- Done at %H:%M:%S.')
else:
time.sleep(0.5)
else:
raise Exception( 'This module is not meant to be imported.' )
I was interviewing at a company and one of the questions was how to detect loops in a linked list.
A linked list is where there are a bunch of objects... perhaps bits of memory that have been allocated... and each one points to the next one in the list. Usually, the last one points to NULL. Sometimes the last one points to the "first" one. But then, in such a list, what does "first" really mean? (Perhaps how you refer to the list as a whole.)
Sometimes you may have a non-circular list where the last element points to an item elsewhere in the list, rather than NULL. Or perhaps you think you have a circular list but the last element does point to NULL. That would be an error. You'd like to be able to detect it... and quickly. To do this, you need to be able to determine if a list has a loop, but you can't just scan through it looking for NULL or the start value, because the "last" item might not point to the "first"; the last node could point to the node just before it. Or the one before that...
This is the sort of thing I probably saw in college but didn't remember. On the spot, I came up with the following algorithm:
bool DoesListLoop( Node const * cur )
{
Node const * base = cur;
int jump = 1;
int remain = 1;
while (cur)
{
cur = cur->next;
if (cur == base) return true;
if (! --remain)
{
jump *= 2;
remain = jump;
base = cur;
}
}
return false;
}
In short, this will race a pointer along the list and every time it has traversed a number of nodes equal to a power of two it resets the base pointer to the current pointer. Each time it moves the "current" pointer ahead it compares it to the base pointer. A match indicates a loop. Finding a NULL means it ended and there is no loop.
More fundamentally, any solution to this problem must advance a pointer through the list forever. If the end of the list is found then there is no loop. If it loops then you will never reach the end, but in order to discern this from an arbitrarily long list you need to match one node with another node previously seen. In order to match loops that loop back to a point arbitrarily far into the list you need to look arbitrarily far ahead of the start, but also arbitrarily far behind the node you are checking in the front. You need to let the "cur" pointer get farther and farther from both what you are comparing against and the start of the list. I did this by resetting the "base" pointer at larger and larger intervals.
Back at the interview, they asked me "do you mean, that you have two pointers, and you advance one pointer two steps for every one step that you advance the other pointer?"
"That sounds like it would work, but, no, I don't mean that." I explained my idea in more detail. They said they thought that it would work, but they wanted to talk about their version some more. Presumably they thought it was a better algorithm (but perhaps they just thought it was simpler and made for a better interview discussion). I think they were wrong. As I've since learned, they meant Floyd's Cycle-Finding Algorithm, published in 1967, also known as "The Tortoise and the Hare Algorithm":
bool DoesListLoop( Node const * cur )
{
Node const * base = cur;
if (!cur) return false;
while (true)
{
cur = cur->next;
if ( ! cur ) return false;
if ( base == cur ) return true;
cur = cur->next;
if ( ! cur ) return false;
if ( base == cur ) return true;
base = base->next;
}
}
As far as performance is concerned, we want to minimize the time (or number of operations) required to determine whether a list is looping or not. We might want to optimize for the non-looping case since that is probably the most likely case (if loops are errors), and we'd like to be able to identify those quickly. We also may have short or long lists, the looping part might be shorter or longer, and the size of the nodes might vary.
This graph shows the number of operations to solve the various cases. Here I take an operation to be a memory fetch to look at the next node. I don't count branching as a cost. (Branch prediction should work very well in this case.) This certainly isn't a perfect estimate, but it does capture what I think proves to be the major cost.
 |
 |
From this simulation we can see that the jumping algorithm is always as good or better than the half-speed algorithm. Although, it should be restated that this is just a simulation of the memory fetching cost. For small lists that can fit entirely into local cache, the cost is only 2/3 of this for the half-speed case. In that case, you would have some cases where using the half-speed was better.
Lighter shades (looping goes back closer to the beginning) generally appear to be harder to solve.
Also note that the performance of the two algorithms don't diverge... they always stay pretty close, at least on a log scale. This confirms that they are of the same order, O(n).
It is nice to see that the theory confirms our expectations, but models are no proof of reality, so let's move on to actual recorded metrics.
I've implemented the algorithms in C++ and timed them on a Linux desktop using low-end hardware with a vintage around 2010.
 |
 |
These results track well with the theoretical results (note the log-log graph). It appears to be more or less a wash until the size reaches well over a million and then (when it no longer fits in cache?) the jumping algorithm takes off.
Here's a graph of the algorithms when looking only at a non-looping list.
 |
 |
Finally, here's the most important graph. Relative performance for verifying a non-looping list, as a function of size of the list. As this would normally by the typical use case, this is therefore the most important graph. If a list did loop, then we wouldn't be as concerned about the performance since we're probably about to report an error and stop the program.
 |
 |
As it turns out, the jumping algorithm isn't really much better than the half-speed algorithm in my theoretically most differentiating test case. From the difference graph it appears that the benefit does continue increasing as the length of the list increases. This indicates that the benefit is not kicking in for a while, presumably because of cache.
Theoretically, not traversing the list twice should yield significant benefits once the memory that is used exceeeds the cache size. (Branch prediction would work very well in this case, but it still needs to get the memory in before it can fetch the next memory location.) This seems to be what we are seeing.
If there are n elements in the list, both of these algorithms will terminate before running through about 2n nodes. They are both O(n). Can we do better? While we certainly can't improve on O(n), perhaps we can run through fewer nodes.
Ideally we'd be able to quickly check if we'd ever seen a node before, and therefore terminate after n nodes when we either find the end or find a node which we've seen before. However, the naive implementation would have us checking each node against each node we've already seen, which makes the algorithm O(n2).
Theoretically, a hash map would let us find whether we'd already seen a point in constant time, but the hash adds and lookups would probably take longer than the 2x multiple that we're trying to remove.
I think this is the best that can be done, excepting, of course, if you can mark flags to indicate if a node has been visited before. The is a page linked to below that has details on this method.
Interestingly, there is an algorithm technically qualifying as O(1) that works on modern computers. Specifically, you can race a pointer along in memory counting how many nodes you've seen. If the count reaches a number higher than you can fit in the memory available, then you must have a loop. This is worst-case O(1) because the number of operations is constant with respect to the list size... it only varies with the size of memory that is available to contain the nodes in the list, which is presumably constant. But if you consider the typical size of linked lists in comparison to even a 32-bit memory address, you can quickly see that this is also about the most inefficient algorithm imaginable. And therefore we have an O(1) algorithm which is probably the least efficient algorithm. Of course, it all depends on what your independent variable "n" represents. If it represents the number of nodes in your list, then this is O(1) (since the number of operations is constant, the memory size, regardless of how large the list is). If it represents memory size, or maximum possible nodes, then this is O(n), and probably much less efficient than the other algorithms listed. Always use an "n" which is meaningful for the analysis.
Performance often depends upon the use case. For instance, if we are usually dealing with a non-looping list and just want to verify that quickly, then a better algorithm might be to track the expected length of the list and just race to the end. If it hasn't ended, then a more exhaustive search could be done. Or, if it is expected to loop, and always to the beginning (circular linked list), then the search can optimize for that.
Suppose there is a prioritized queue of elements. The elements are allocated as a std::vector because changing the size is infrequent and the number only ever grows. The elements refer to each other through offsets. The order rearranges as the priority of the various items shift around. For whatever reason, we want to be sure that the list terminates and doesn't loop. (Perhaps we are implementing the priority queue for Dijkstra's algorithm.) What is the most efficient way to do this? I suspect that the answer is in the previous (silly) section.
One day my boss came out of his office and said "I've got to get the highest hundred values of a bunch of data. I tried sorting it, but it's just taking too long."
He had many Megabytes of floats, and was trying to sort the whole thing in order to find the highest 100 values. There are two immediate approaches to this problem:
Both of these are obviously unacceptable. In Big O notation the first option is (with typical QSort, MergeSort, et c.) an O(N*log(N)) operation, and my boss was already trying it. With the example numbers, we're looking at O(N*log2(N)) = O(1x106*20) = O(2x107) operations.
The second option can be optimized a bit, but you need to be prepared to do an insertion sort for every one of your one million items. In practice, you would compare the item from the M list against the smallest value in your N list, and if it was smaller and the N list was already full, then you'd skip the insertion. In Big O notation, this is O(N * M) = O(1x108) operations.
Which one is worse depends on the values of N and M.
As an interesting corner case, what if the list is already sorted, or nearly so? The first option (Sort N and Pick M) can possibly fall apart, since the simplest Quicksort implementations have trouble with this case. The second option (Scan N and Sort M) will also fall apart, since it will always have to insert each new entry into the N list (unless the M elements are positioned at the end, in which case it falls prey to a reverse sorted list).
Another way to do this is to do something like a quicksort, but without recursing on the side of the pivot that doesn't contain the element of interest. This is called Quickselect, and generally has time O(N), but worst case O(N2). For sufficiently evenly distributed elements this would first process all elements, then half the elements, then a quarter, et c. The total number of elements processed converges to 2*N.
There is an STL algorithm to do this: nth_element. There is also a similar function, partition, that will take the pivot value. partial_sort will sort values up to a specific position in the list.
I wrote a Python script to draw some pretty graphs of performance, and also a C++ program to provide the metrics. I also have the specific results file graphed here.
First a note on how to read the graphs. Time is the y axis, so lower values are better. N is the X axis, so values to the right are operating on larger sets of data. I've color coded datapoints by algorithm (red, green, blue), and shaded them by the value of "M". Lighter shades correspond to smaller areas being sorted.
I've also produced some theoretical performance graphs. These are not calibrated to actual performance. They should not match up with the actual metrics except that they should have the same sort of shape.
"Sort N Pick M" sorts the entire sequence of N items, then picks out the first M items. I've provided results for two implementations. One uses the STL and one uses qsort. The qsort variety must call a user-provided function to compare the items, whereas the STL version can inline that call. The STL version seems to be doing better across the board, with the STL clocking at 0.000738 milliseconds versus 0.002162 for a datapoint near 10,000. Since these are log graphs you can see that the STL seems to be consistently about thrice as fast as using qsort, regardless of N. Yay STL!
Regardless of how many items are picked out (M) it takes about the same amount of time to run this algorithm. Since the results are all contiguous after the sort, that range can be returned without requiring a copy of the M elements. Even if this was necessary, the time to do this, O(M), is much less than the time to sort, O(N*log2N), and would not be particularly noticeable in the timing.
Notice the odd jog near N equal to one million. I looked into that, but the results aren't relevant to this discussion. (I may post details in the future.)
The second algorithm looks much different. This is essentially an insertion sort where it doesn't bother inserting if the new value is known to not fit in the M "best" items. Imagine that M is one, how fast would it be? Pretty fast, given that it is essentially doing min() on N items. That is an O(N) operation, and a fast one at that. What about if M is near N? Pretty slow, since insertion sort is an O(N2) operation. Unless M is really near to N, in which case the initial qsort on the M items has already done just about all the work. That explains the initial low values on the graphs for the higher values of M (notice how they track the "Sort All" time from the graphs combining multiple algorithms).
There is a graph above that compares all the algorithms. It shows that for small values of M this algorithm can be faster than any of the others, but for the general case it is much slower.
How often are inserts required? The likelihood is M/i where i is the position of the element. How many inserts are required, then? Sum as i=M to N of M/i. Integrate from M to N the function M/x... I believe that would be M*ln(N)-M*ln(M) = M*ln(N/M).
Below is a graph of the expected time to do an insertion sort to find the M lowest items of N items, where the M items are initially sorted, and then the remaining items are insertion sorted. This graph, however, has M as the x axis. Increasing M increases the total time, except near the end when M is nearly N and most items are efficiently dealt with by the O(M*log2M) sort. I have plotted the time to do a qsort on the entire list of N items for comparison, and each value of N impacts the qsort line when M reaches N.
However, that graph is a bit misleading since it appears that only very large values of M as compared to N will yield a performance gain. This is because the x axis is presented with logarithmic progression. Actually the worst case is somewhere around half to two-thirds, as can be seen by the graph below which shows the same data but displays the x axis linearly.
The graph of the nth_element algorithm is not too suprising. It operates mostly without regard to the value of M, as expected. It is noticably faster than the Sort N Pick M algorithm. This algorithm is O(N), so it should be considerably faster than the O(N*log2N) algorithm of Sort N Pick M.
But why does it appear to have the same slope as the SortN Pick M algorithm? Consider the difference implied by additional multiple of log2N. Log2(N) equals 16.6 for N=100,000 and 19.9 for N = 1,000,000. The increase of the red lines should be 20% more than for the green. That 20% should correspond to the width of the fifth largest tickings on the left hand side. That is a fairly small tick. In other words, after the number get into the millions the log part doesn't affect the result very much incrementally. If the graph went to smaller numbers, or if the y axis was linear instead of logarithmic, then the curve would likely be more obvious.
By far, insertion sort is the best performing algorithm. Well, at least for small values of M. It's too bad I can't get the best of both worlds... Insertion Sort time for small M, and Partition time for larger M. Of course, I could always compare M to N and decide which algorithm to use, but that seems so hacky.
Why am I doing an insertion sort at all, when I don't really care what the sorted order is, but just what the highest values are?
Heaps are neat. They are a not-quite-sorted,-but-maybe-sorted-enough type of data structure. Heaps can insert in O(log2N) time. A Heap can be constructed in O(N) time! (Knuth, The Art of Computer Programming , volume 3, section 5.2.3, page 155.)
Heaps always know what their highest item is, because it is in position 0. Heaps work by having the property that the element at index i is always greater than the elements at indices 2*i+1 and 2*i+2 (for the first element being at index 0). They can be thought of as a nearly balanced binary tree where each node is greater than its children. It is not a red/black tree or any other type of sorted list.
To insert you figure out where the next item goes (index i, where i is the current length of the list) and put the new item there. Then you percolate that point up:
To pop the highest item, you remove the last item in the list and put it in the list, either as its own sibling, or as the parent, as required upon comparison with the sibling. If a sibling is replaced, it replaces the common parent, which in turn gets to replace its sibling or parent. Eventually you get to the root of the heap and it is taken away as the highest value before the location is overwritten.
The Heapsort algorithm takes an unordered list, turns it into a heap, then burns through the heap, popping off the highest item and placing it in place of the last item. The result is a sorted list. Heap construction takes O(N) time, but the popping takes O(N*log2N) time, same as other sorts. The advantage of Heapsort is that this neither takes additional memory (like merge sort) nor has a work case scenario of O(N2) (like Quicksort). Typical run time is worse than Quicksort, however.
Heaps are ideal for priority lists that will be modified while in use. They can fetch first, insert, and delete items in O(log N) time. This makes them good choices for Huffman Encoding.
What can't heaps do? Well, you can't traverse a heap in sorted order very easily... you basically have to pop off all the items in turn. They are most useful when you just need the highest item, or when the number of inserts and deletes is significantly larger than the size of the heap for each time it is walked in a sorted order.
Instead of using an Insertion Sort, if I just maintain the lowest M items as a heap, then I can easily compare to the highest value, even after an insertion. For evenly distributed numbers, the likelihood of needing to insert into N is M/i where i is the index of the current point. If an insertion is needed it will take O(log2N) instead of O(N) for an insertion sort.
If I do this then we can cut down on the time required for the inserting part of the insertion sort. The result will need a final sort pass if we need items in the correct order instead of just the items listed (this is also true of the nth_element version).
Another possible use of a heap would be to heap the entire list, then pull out the top M items. The performance of this is quite simple: O(N) to heap, then M*log(N) to pull out the items. (Note that the depth of the tree decreases, thereby reducing the log(N) component as items are pulled out. Given that the log(N) value holds for half the items, even if the other half takes zero time it would still be the same O(M*log(N)).)
However, as can be seen from the graph below, this new algorithm never appears to be better than using a heap for an insertion sort. It only becomes competetive well after using nth_element would have beaten both Heap algorithms.
The performance does still get worse than the nth_element case. But instead of being about 100x as slow (or more) the Heap implementation seems to max out at about ten times as slow. (Below is a graph of all the implementations.)
| Algorithm | Complexity |
|---|---|
| Sort N and Pick M (QSort) | O(N*log2N) |
| Scan N and Pick M (Insertion sort) | O(M*log2M + (N-M)*M) |
| nth_element | O(N) |
| Heap insertion sort | O(M + (N-M) + log2(M)*ln(N/M)) |
| Heap All and Pop | O(N + M*log2(N)) |
Here is a graph of the theoretical complexity of the algorithms.
The theoretical analysis of the complexity of the algorithms indicates that the Heap insertion sort is the fastest for small M, but that it does grow without bound on m. While it may always be faster for any N on small values of M, there will be values large enough to justify using nth_element instead.
For low M, the Heap and Insertion sort methods have the same performance. This makes sense, since the benefit of using a heap over a straight sorted list is log2(M) versus M when inserting and M versus M*log2(M) for the initial sort. As M approaches one these approach equivalence.
Bottom line: the Heap Insertion Sort is always at least as good as the regular insert sort, but can still be beat by nth_partition for larger values of M.
Finding the Highest M of N by Mark Santesson is licensed under a Creative Commons Attribution 3.0 Unported License.
I've interviewed several people for C++ positions and one question we always ask is what a virtual destructor is and when to use one. For some reason, a suprising number of people say that you should make your destructor virtual whenever you have anything else in the class that is virtual. That is not the correct answer. (Although, it is suggested by Bjarne Stroustrup in the ARM (page 278), and I suppose that is a pretty good basis for the claim...) There may be a correlation between the two, but there is absolutely no causative relationship.
There are three reasons that must all be fulfilled(*) before making a destructor virtual.
Technically, you should ignore that last one. The standard says:
5.3.5 Delete
[...]
3 In the first alternative (delete object), if the static type of the operand is different from its dynamic type, the static type shall be a base class of the operand's dynamic type and the static type shall have a virtual destructor or the behavior is undefined. In the second alternative (delete array) if the dynamic type of the object to be deleted differs from its static type, the behavior is undefined.
(Emphasis mine.)
Which means: if you're going to delete an object of class B through a pointer to class A (where B is derived from A), then A had better have a destructor that is virtual. That doesn't mean that it needs to declare it virtual itself but if one of A's superclasses doesn't declare the destructor virtual then A's destructor does need to be declared as virtual. And if you intend to rely on a higher base class declaring it virtual, you should probably just declare it so as well... in case someone does something utterly foolish like making it no longer virtual.
If that doesn't convince, see what some learned elders have to say on it:
However, if you feel like living dangerously, or even if you don't but you really need that extra performance, then you might be able to get away with it.
Now, normally I'm really a fairly honest person. Really! And I'm a big advocate of not lying to the compiler. (Generally, it takes its revenge.) But sometimes lying is just communicating something in a different way. In this case, I'm saying to the compiler: "I know you really want to dot your I's and cross your T's, but believe me, in this case you really don't need to. Just call the destructor of the type of the pointer."
That said, you do still have to be really careful. There are a few reason why you really would need to have the derived class's destructor called:
If all of those reasons are absent, then you might be able to
get away with not having your class use virtual destructors.
Related to the discussion about when a function needs to be virtual, is when can an array of a derived class be deleted through a pointer to a base class? If the sizes are the same (and assuming you don't have to worry about the destructor not being virtual), then the answer is whenever you like. If they aren't the same, then never.
To see why, imagine that you have class A and B, where B derives from A, and both hold an integer. A always sets it to 1, and B sets it to 2. Something like (source here):
class A {
int nDataA;
A() : nDataA(1) {}
};
class B : public A {
int nDataB;
B() : nDataB(2) {}
};
Creating B[3] dynamically, deleting through B*
Constructing at 0xd915c
Constructing at 0xd9168
Constructing at 0xd9174
Dest of 0xd9174. I am now B :(size is 12 bytes) B83F0400 01000000 02000000
Dest of 0xd9174. I am now A :(size is 8 bytes) 08400400 01000000
Dest of 0xd9168. I am now B :(size is 12 bytes) B83F0400 01000000 02000000
Dest of 0xd9168. I am now A :(size is 8 bytes) 08400400 01000000
Dest of 0xd915c. I am now B :(size is 12 bytes) B83F0400 01000000 02000000
Dest of 0xd915c. I am now A :(size is 8 bytes) 08400400 01000000
Creating B[3] dynamically, deleting through A*
Constructing at 0xd915c
Constructing at 0xd9168
Constructing at 0xd9174
Dest of 0xd916c. I am now A :(size is 8 bytes) 08400400 02000000
Dest of 0xd9164. I am now A :(size is 8 bytes) 08400400 B83F0400
Dest of 0xd915c. I am now A :(size is 8 bytes) 08400400 01000000
(These results were obtained with the DJGPP compiler, which uses gcc.)
Notice how it deletes backwards; it starts at 0xd916c and goes down to 0xd915c. Also notice that those aren't the addresses that were constructed, unlike the first case where we destroyed through a B pointer. Notice what happens when you call it through Bs destructor: it starts with the vptr at 00043FB8 and calls ~B, then sets it to 00044008 for when it calls ~A. This is as expected, of course, since when you call through the constructors and destructors, virtual functions resolve to the current class being constructed/destructed, not the class that the object will eventually be.
Now look at the sequence of destructor when it is done through the A* pointer. The first one that is destroyed is destroyed through a pointer that is actually pointing to the "1" of the second item. Before the ~B code is called the vptr for A's vtable is written on top of the "1". The same goes for the second item, which starts out pointing to the "2" of the first item.
Clearly this is bad. Unfortunately, even making the destructor of A
virtual will not solve this problem. Theoretically, if the class being
pointed to has a vtable it would be possible to encode the sizeof in
the table and use that when iterating through the array. Or, the compiler
could store the sizeof in the table, as it stores the number of
entries in the array. Gcc doesn't do this, for better or worse. The
bottom line is that if you want to destroy an array of Bs with a
pointer to As, then sizeof(B) must equal sizeof(A), in addition to
the other rules stated above, regardless of whether or not the destructor
is virtual.
You could ensure that class A is not ever deleted in array form by overloading that operator and throwing an exception, but then how do you know that you aren't just deleting a bunch of "A"s, which is fine? (If you overload the delete array operator for "B" (in order to throw), then it will only get called in the instance where it is being deleted properly, which is actually worse than doing nothing.)
You could implement a custom destructor for arrays of A, and test in the
destructor if it is seeing an object of class B in order to handle it specially.
But you would still have the wrong pointer to the class... you'd have to
fix that up with pointer math after you figure out what your base is.
This is so terrible that I refuse to think about it anymore.
There is a performance penalty to making and calling a virtual destructor. Making a destructor virtual will force the class to store a pointer (called a vptr) to the class's virtual table. If there are no other virtual functions in the class, then this is a little bit of extra overhead (whatever the pointer size is: usually 32 bits, but sometimes 64 bits or even something else). This is probably where the typical erroneous answer comes from. Presumably people think that if you are already paying the space cost, then you might as well make the destructor virtual.
There is also a performance penalty to calling a virtual function,
including virtual destructors. The vptr must be dereferenced and the
resulting function called. This can cause memory cache misses, et c.
There you go. Be careful. Or just play it safe and follow the standard. Or did I miss something?