tungwaiyip.info

home

about me

links

my software

Media

Yucatán Photos

St Lucia Photos

Photo Album

Videos

Blog

< June 2005 >
SuMoTuWeThFrSa
    1 2 3 4
5 6 7 8 91011
12131415161718
19202122232425
2627282930  

past articles »

Click for San Francisco, California Forecast

San Francisco, USA

 

Python's half open index notation

Beginner programmers often wonder about Python's sequence indexing and slicing notation. Array index starts from 0. Slicing uses half open notations, where L[a:b] is a subsequence with index x where a <= x < b.

Why is the endpoint excluded? Isn't it more intuitive if array index starts from 1 and the endpoint is included, so that a 3 elements array is referenced as L[1:3] with items L[1], L[2], L[3]?

It turns out this notation is an elegant and deliberate design and it has some excellent properties.

We write programs to operate on arrays, to find their length, traverse the subsequences, split them or join them. The half open notation always show a simple pattern. But the inclusive notation often requires adding 1 or substracting 1 to the indexes in many operations. Thus it is more vulnerable to off-by-one-error. This article One True Way of array indexing discuss this at length. I have reproduce its example (with corrections) below:

Operation Half open Inclusive
length of a slice L[a:b] b-a (b-a+1)
first n characters of L L[:n] L[1:n]
last n characters of L L[-n:] L[len(L)-n+1:]
The identity slice L == L[0:len(L)] == L[:] L[1:len(L)]
The empty slice L[a:a] is empty for any a. perhaps L[a:a-1]?
A slice of length n, from point a L[a:a+n] L[a:a+n-1]
Split L[a:b] at index c L[a:b] == L[a:c]+L[c:b] L[a:c-1]+L[c:b]

Another important property is an empty sequence can be expressed by L[a:a], while there is no natural way to express an empty sequence with the inclusive notation. But do we really need to care about a special case? Absolutely! In fact failure to account for empty input is one of the most common error. Just like zero is a fundamental concept in mathematics, always think how you program can handle null input. An inferior approach is to represent empty sequence by None or null pointer. This creates a special case so that a variable need to be tested before dereferencing. Failure to do so contributes to unexpected exceptions. It is an elegant design that L[a:b] can also represent sequences with 0 length.

C++'s STL also choose this notation to represent a range. According to the literature this is crucial because "algorithms that operate on n things frequently require n+1 positions. Linear search, for example (find) must be able to return some value to indicate that the search was unsuccessful." I have seen so many people flunked link list or data structure exercises because they have trouble dealing with the end of a list. Often a good solution is shift the focus beyond the n concrete objects to the n+1 positions around them. I hope this help to make sense of the half open notation.

2005.06.16 [, ] - comments

 

 

blog comments powered by Disqus

past articles »

 

BBC News

 

Hamas vows to continue Gaza battle (29 Jul 2014)

 

US and EU expand sanctions on Russia (29 Jul 2014)

 

Last Hiroshima bomb crew member dies (29 Jul 2014)

 

Child malaria vaccine 'milestone' (29 Jul 2014)

 

China spies 'hacked Canada agency' (29 Jul 2014)

 

Migration changes 'to put UK first' (29 Jul 2014)

 

West Africa flight ban over Ebola (29 Jul 2014)

 

Jewish Museum suspect extradited (29 Jul 2014)

 

China investigates ex-security chief (29 Jul 2014)

 

Death threats to Amazon tribe leader (29 Jul 2014)

more »

 

Slashdot News for nerds, stuff that matters

 

The Hobbit: the Battle of Five Armies Trailer Released (2014-07-30T00:59:00Z)

 

Old Apache Code At Root of Android FakeID Mess (2014-07-29T23:58:00Z)

 

35% of American Adults Have Debt 'In Collections' (2014-07-29T23:14:00Z)

 

EA Tests Subscription Access To Game Catalog (2014-07-29T22:54:00Z)

 

Which Is Better, Adblock Or Adblock Plus? (2014-07-29T22:32:00Z)

 

A Look At the Firepick Delta Circuit Board Assembler (Video) (2014-07-29T21:50:00Z)

 

seL4 Verified Microkernel Now Open Source (2014-07-29T21:08:00Z)

 

Enceladus's 101 Geysers Blast From Hidden Ocean (2014-07-29T20:28:00Z)

more »

 

TechPsychic Tech Rumors and Invented News

more »

 

SF Gate

 

Bay Area News (7 Jan 2012)

 

City Insider (11 Feb 2012)

 

Crime Scene (13 Feb 2012)

 

C.W Newius Column (10 Jan 2012)

 

C.W. Nevius Blog (11 Feb 2012)

 

Education News (10 Jan 2012)

 

KALW (11 Feb 2012)

 

Matier and Ross Blog (11 Feb 2012)

 

Communications platform would link electric cars, utilities (29 Jul 2014)

 

Medical marijuana users link to delivery services with Eaze (29 Jul 2014)

 

Dollar Tree spending .5 billion for Family Dollar Stores (28 Jul 2014)

 

Dollar Tree buying Family Dollar for .5 billion (28 Jul 2014)

 

23andMe helps make new Parkinson's disease discovery (28 Jul 2014)

 

Fliers love Virgin America, but will investors love its IPO? (28 Jul 2014)

more »

 

Asia Times Online

 

Russia told to pay in Yukos case (Tue 29 Jul 2014 11:00:00 GMT)

 

Vietnam buckles under Chinese pressure (Tue 29 Jul 2014 11:00:00 GMT)

 

CHAN AKYA An era of thugs (Tue 29 Jul 2014 11:00:00 GMT)

 

Why no Arab state cries for Gaza (Tue 29 Jul 2014 11:00:00 GMT)

 

COMMENT The resistance will not be crushed (Tue 29 Jul 2014 11:00:00 GMT)

 

The Pashtun factor in Pakistan's insurgency (Tue 29 Jul 2014 11:00:00 GMT)

 

JOHN PILGER Palestine, war and lethal reporting (Tue 29 Jul 2014 11:00:00 GMT)

 

Central Asia clash mars China gas plan (Tue 29 Jul 2014 11:00:00 GMT)

 

THE BEAR'S LAIR Business and free markets (Tue 29 Jul 2014 11:00:00 GMT)

more »

 


Site feed Updated: 2014-Jul-29 19:00