## Coding: Fleeting Thoughts

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Coding: Fleeting Thoughts

Thesh said "numbers between 0 and 2", a width-2 range, not "integers between 0 and 2", a 3-element set.

If they meant a 3-element set, tho, you're right.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Flumble
Yes Man
Posts: 2264
Joined: Sun Aug 05, 2012 9:35 pm UTC

### Re: Coding: Fleeting Thoughts

if your being padentic: there's either only 1 number between 0 and 2 (namely 1) or there are (un)countably many.

Thesh
Posts: 6598
Joined: Tue Jan 12, 2010 1:55 am UTC

### Re: Coding: Fleeting Thoughts

As someone who has worked a lot with SQL Server, between 0 and 2 means [0,2]
Summum ius, summa iniuria.

Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Coding: Fleeting Thoughts

Flumble wrote:if your being padentic: there's either only 1 number between 0 and 2 (namely 1) or there are (un)countably many.

Uh, no. First, I very specifically said "integers". Second, I didn't specify whether the range was inclusive or exclusive on either end, so anywhere between 1 and 3 integers are "between" 0 and 2. jaap and I both talked about 3, tho, so it's clear from context that I meant the range to be inclusive on both ends.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: Coding: Fleeting Thoughts

Flumble wrote:if your being padentic: there's either only 1 number between 0 and 2 (namely 1) or there are (un)countably many.

Sure, if you believe in non-constructible numbers like a ponce.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

### Re: Coding: Fleeting Thoughts

So, here's a fun thing I recently discovered, thanks to this thread...

Say you have a JavaScript file which is served without any encoding information in the content-type header. Say it has some UTF-8 encoded text in string literals, rather than using \u escapes. Then say you include that JS in an HTML page.

If that HTML page is served as UTF-8, the browser will parse the JS file as UTF-8, but if the HTML is served as ISO-8859-1, the browser will parse the JS as ISO-8859-1. You can override this with an attribute on the script tag, but this is what it does by default.

Or, at least, that's what Firefox seems to be doing.

I'm not even sure that's wrong, on average as a guessing strategy, but... it's not exactly what I was expecting it to do.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

hotaru
Posts: 1045
Joined: Fri Apr 13, 2007 6:54 pm UTC

### Re: Coding: Fleeting Thoughts

well, you really should be specifying the encoding in the Content-Type header, and if you don't, you're not in any position to complain about anything the browser does.

Code: Select all

factorial product enumFromTo 1
isPrime n
factorial (1) `mod== 1

Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Coding: Fleeting Thoughts

Yeah, for legacy reasons, if an included resource doesn't specify its own encoding (either through headers or thru some inline mechanism like @charset in CSS), it usually inherits the encoding of the including document. There are a few exceptions now that simply always assume UTF-8, but JS and CSS are not among those.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Xeio
Friends, Faidites, Countrymen
Posts: 5101
Joined: Wed Jul 25, 2007 11:12 am UTC
Location: C:\Users\Xeio\
Contact:

### Re: Coding: Fleeting Thoughts

Code: Select all

if(result != null && result.Rows.Count > 0)
{
foreach(var row in result.Rows)
{
//Non-branching logic here
break;
}
}
This makes me irrationally angry.

Flumble
Yes Man
Posts: 2264
Joined: Sun Aug 05, 2012 9:35 pm UTC

### Re: Coding: Fleeting Thoughts

ucim
Posts: 6892
Joined: Fri Sep 28, 2012 3:23 pm UTC

### Re: Coding: Fleeting Thoughts

What is even wrong with it? I assume you take exception to the (in this case unneeded) break statement, but in a situation where similar coding structures elsewhere may have branching code, the break acts as a bit of protective scaffolding for the changes that may come later.

A little like wasting clock cycles initializing pointers. Because you'll mever nake a mistake.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Heartfelt thanks from addams and from me - you really made a difference.

Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: Coding: Fleeting Thoughts

He takes exception to the loop that always breaks on the first iteration, thus fundamentally violating the first law of loops. That they loop.
Last edited by Yakk on Thu Mar 03, 2016 12:12 am UTC, edited 1 time in total.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Contact:

### Re: Coding: Fleeting Thoughts

ucim wrote:What is even wrong with it? I assume you take exception to the (in this case unneeded) break statement
The break statement is needed (perhaps). What's not needed is the whole loop! Not to mention the redundant check for result.Rows.Count > 0.

ucim
Posts: 6892
Joined: Fri Sep 28, 2012 3:23 pm UTC

### Re: Coding: Fleeting Thoughts

Yakk wrote:...that always breaks on the first iteration...
Ach so.
EvanED wrote:redundant check for result.Rows.Count > 0
Why is that redundant? Is it not possible that result could exist but have zero rows? (depends on how result is generated, I suppose). Just checking for result.Rows.Count should at least generate a warning if result does not exist. (depending on language, I suppose)

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Heartfelt thanks from addams and from me - you really made a difference.

Carlington
Posts: 1588
Joined: Sun Mar 22, 2009 8:46 am UTC
Location: Sydney, Australia.

### Re: Coding: Fleeting Thoughts

I had a conversation with an old friend last night, during which he told me about an idea he's had. His description of the problem got me thinking, so I thought I'd come to pick you lot's brains, if it's okay.

What we have is, in general terms, an arbitrary number of objects, some of which link to others. The links are always one-directional, so there's no straightforward way to, for example, generate a list of all objects that link to a given object - only a list of all objects that a given object links to. The question he aims to answer is: for any two objects, is there a path between the two? My initial intuition says that the most efficient way to solve this would be to programmatically construct a map (is the term I want "directed graph"?) of all objects and their links, and traverse this to find whether there is a path between the two.
My initial thought was that if we generate the map and then make every link bi-directional, we can traverse in both directions and thus speed things up - but it occurs to me that order ought to be preserved. I also wonder whether it's faster to build the map for everything and store it, and then search it each time, or to build just the paths for the relevant objects as we need them and never build the whole graph. I suspect the answer is "depends on how many objects you have".
Is there some better way of doing this that I don't know?
Kewangji: Posdy zwei tosdy osdy oady. Bork bork bork, hoppity syphilis bork.

Eebster the Great: What specifically is moving faster than light in these examples?
doogly: Hands waving furiously.

Please use he/him/his pronouns when referring to me.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Contact:

### Re: Coding: Fleeting Thoughts

ucim wrote:
EvanED wrote:redundant check for result.Rows.Count > 0
Why is that redundant? Is it not possible that result could exist but have zero rows?
Yes, in which case the loop won't execute because of the test. But what if you omitted the test? Then the loop would execute zero times. Soooo... same thing! There's nothing else in the body of the if.

Flumble
Yes Man
Posts: 2264
Joined: Sun Aug 05, 2012 9:35 pm UTC

### Re: Coding: Fleeting Thoughts

A bi-directional search can help greatly in large graphs with long median shortest paths. But for graphs less than millions of nodes it shouldn't matter.

If you want to know the reachability of only a few nodes, you can use a breadth-first traversal of your directed graph (you don't need to actually copy it to such a structure, just traverse it like it is one); or if you somehow have a heuristic, A*.

If you want to know the reachability/distances of all nodes, take a look at Floyd-Warshall. Or, in case you want to know the reachability of nodes in an undirected graph, it's equivalent to graph coloring/finding components.

If you want to know the reachability of one node from all the others, it's also kind of like graph coloring.

Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: Coding: Fleeting Thoughts

Carlington wrote:for any two objects, is there a path between the two?

Have two sets -- visited and edge.

Pick one of the two objects. Put it in both visited and edge.

Repeat until edge is empty:

Take an element out of edge. Add every element not in visited to both visited and edge.

End repeat.

If at any point you add the *other* object to visited, stop the above algorithm and return "found a path". Otherwise, there is no path.

Now do this for the other object as well for paths "going the other way". Or at the same time.

This can be improved if you have a good heuristic for picking a "more likely path" to find the other party (say, "closer on a grid" or somesuch) to pick an edge from the edge set. Or even "number of nodes away from the start node", which has the nice property that close links get solved quickly.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

ucim
Posts: 6892
Joined: Fri Sep 28, 2012 3:23 pm UTC

### Re: Coding: Fleeting Thoughts

Xeio wrote:

Code: Select all

if(result != null && result.Rows.Count > 0)
{   foreach(var row in result.Rows)
{  //Non-branching logic here
break;
}
}
This makes me irrationally angry.

EvanED wrote:But what if you omitted the [result.Rows.Count > 0] test? Then the loop would execute zero times.

If the method that generates result returns a non-null non-array (e.g. an error message string) on some errors, and a null on others, the foreach would complain (depending on language) if being fed a nonexistent result.Rows (because foreach wants an array, and result happens to be a non-null non-array object).

I suppose something would complain if result is a non-null non-array object without a Rows.Count element, so to be safe one would need:

Code: Select all

if (result != null && is_array(result) && is_set(result.Rows.Count) && is_int(result.Rows.Count) && result.Rows.Count > 0)
{   //whew!
do stuff
}
At what point does belt and suspenders hoist one by one's own petard?

I try to code to get no warning and no notices. Even if (now) it's harmless to reference a non-existent variable, in the future it might lead to mustard. But all those tests make code harder to read and debug in the first place.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Heartfelt thanks from addams and from me - you really made a difference.

Thesh
Posts: 6598
Joined: Tue Jan 12, 2010 1:55 am UTC

### Re: Coding: Fleeting Thoughts

The language is C#. If result.Rows is null, result.Rows.Count throws an exception. If result.Rows.Count == 0, then the loop does nothing, meaning the check is useless.
Summum ius, summa iniuria.

ucim
Posts: 6892
Joined: Fri Sep 28, 2012 3:23 pm UTC

### Re: Coding: Fleeting Thoughts

Thesh wrote:The language is C#.
Thanks. I'm not familiar with musical computer languages.

What does C# do in a foreach when fed a non-array to loop through?

PHP silently complains. If C# is happy with it, then yes, I see that the extra test is useless.

(and if testing a nonexistent variable (i.e. result.Rows.Count) against zero makes it complain, then the test is harmful.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Heartfelt thanks from addams and from me - you really made a difference.

phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

### Re: Coding: Fleeting Thoughts

I don't know much about C# but I know it's a statically typed language (or at least, it normally is, iirc it has a dynamic option but you have to be explicit about it). So "result" is either going to be null, or be an instance of whatever the database result class is. So if result is not null, then result.Rows would exist, and would have to be an array (or itself null, but that's likely contractually obliged to not happen), so it would have a .Count, which would have to be an int.

The theory that result could be an array, or maybe an error message string, is unlikely. Wherever you're getting it from is far more likely to be reporting its errors via exceptions, than with some sort of dynamically-typed return value.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

Xeio
Friends, Faidites, Countrymen
Posts: 5101
Joined: Wed Jul 25, 2007 11:12 am UTC
Location: C:\Users\Xeio\
Contact:

### Re: Coding: Fleeting Thoughts

phlip wrote:So "result" is either going to be null, or be an instance of whatever the database result class is. So if result is not null, then result.Rows would exist, and would have to be an array (or itself null, but that's likely contractually obliged to not happen), so it would have a .Count, which would have to be an int.
One thing to note about C#, the standard practice is to never return a null array or collection, always an empty one. So yes, checking result.Rows for null would be redundant.

Granted, badly written libraries can return null anyway, but it's a safe assumption at least in the .Net framework.

phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

### Re: Coding: Fleeting Thoughts

Sounds like an eminently sensible convention to have... I've worked with a project that returned nulls instead of empty lists, it just meant more work for the caller and more work for the callee, and no-one really benefited.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

ucim
Posts: 6892
Joined: Fri Sep 28, 2012 3:23 pm UTC

### Re: Coding: Fleeting Thoughts

phlip wrote:Sounds like an eminently sensible convention to have... I've worked with a project that returned nulls instead of empty lists, it just meant more work for the caller and more work for the callee, and no-one really benefited.
What if the reason a list was empty mattered? For example, "there were no results that matched" is a legitimate empty list, but "the database is down so I have no answer for you" would be illegitimate as an empty list. I suppose one could count on the database query throwing the exception, but that doesn't sound good.

(I've been away from programming for a long time; exceptions are not something I'm really familiar with, and they look a lot like GOTOs to me.)

What I sometimes do is have the function that's hopefully returning an array, do so as one member of another array or struct, the other member being an exit code or error code. So, the calling function can check the exit code and know whether the actual returned value is usable. But I guess that's old school.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Heartfelt thanks from addams and from me - you really made a difference.

phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

### Re: Coding: Fleeting Thoughts

ucim wrote:What if the reason a list was empty mattered? For example, "there were no results that matched" is a legitimate empty list,

Well, in the specific case I'm talking about, these were legitimate empty lists, it was just returning null instead. That is, the code was full of stuff like:

Code: Select all

if (this.list == null)
this.list = new List();
}
void removeValue(v) {
this.list.remove(v)
if (this.list.isEmpty())
this.list = null;
}
void List getFilteredList(stuff) {
if (this.list == null)
return null;
List filteredlist = new List();
for (i : this.list) {
if (matches filter) {
}
}
if (filteredlist.isEmpty())
return null;
else
return filteredlist;
}
// ...
// then when we want to call it
List l = obj.getFilteredList(etc);
if (l == null) {
handle empty list as a special case
} else {
handle list with values in it
}
It was all completely pointless and I have no idea what, if any, benefits there were.

ucim wrote:but "the database is down so I have no answer for you" would be illegitimate as an empty list. I suppose one could count on the database query throwing the exception, but that doesn't sound good.

That's actually a pretty perfect example of a situation that would warrant an exception. If you were an environment where exceptions were the normal way of handling errors, and the database was down, and it didn't throw an exception, I'd consider that a bug.

ucim wrote:(I've been away from programming for a long time; exceptions are not something I'm really familiar with, and they look a lot like GOTOs to me.)

Try/catch could... maybe be considered goto-like statements with structure? But then the same could be said of "if", loops, or any other flow-control construct in a language. Goto-like statements with structure is, like, the entirety of what flow-control statements are.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

Breakfast
Posts: 117
Joined: Tue Jun 16, 2009 7:34 pm UTC
Location: Coming to a table near you

### Re: Coding: Fleeting Thoughts

phlip wrote:
ucim wrote:What if the reason a list was empty mattered? For example, "there were no results that matched" is a legitimate empty list,

Well, in the specific case I'm talking about, these were legitimate empty lists, it was just returning null instead. That is, the code was full of stuff like:

Code: Select all

if (this.list == null)
this.list = new List();
}
void removeValue(v) {
this.list.remove(v)
if (this.list.isEmpty())
this.list = null;
}
void List getFilteredList(stuff) {
if (this.list == null)
return null;
List filteredlist = new List();
for (i : this.list) {
if (matches filter) {
}
}
if (filteredlist.isEmpty())
return null;
else
return filteredlist;
}
// ...
// then when we want to call it
List l = obj.getFilteredList(etc);
if (l == null) {
handle empty list as a special case
} else {
handle list with values in it
}
It was all completely pointless and I have no idea what, if any, benefits there were.

ucim wrote:but "the database is down so I have no answer for you" would be illegitimate as an empty list. I suppose one could count on the database query throwing the exception, but that doesn't sound good.

That's actually a pretty perfect example of a situation that would warrant an exception. If you were an environment where exceptions were the normal way of handling errors, and the database was down, and it didn't throw an exception, I'd consider that a bug.

ucim wrote:(I've been away from programming for a long time; exceptions are not something I'm really familiar with, and they look a lot like GOTOs to me.)

Try/catch could... maybe be considered goto-like statements with structure? But then the same could be said of "if", loops, or any other flow-control construct in a language. Goto-like statements with structure is, like, the entirety of what flow-control statements are.

Also, more and more C# is starting to catch and then return exceptions in result objects rather then throwing them further up the call stack. So you'll still see try / catch inside of methods but you're letting callers decide how to deal with an exception instead of requiring them to deal with it.

Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: Coding: Fleeting Thoughts

Wait, you are saying that come-froms sprinkled through code are not ideal for maintenance and reliability?

Whodathunk.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Posts: 1827
Joined: Sun Oct 19, 2008 5:28 pm UTC
Location: Space Florida

### Re: Coding: Fleeting Thoughts

ucim wrote:(I've been away from programming for a long time; exceptions are not something I'm really familiar with, and they look a lot like GOTOs to me.)
Exceptions store a lot of information on where and how they were produced , so it's generally pretty clear how the from and to are connected, unlike with GOTO statements.

Many code inspection tools will flag cases where exceptions are thrown and caught in the same function, because that is far too like a GOTO.

As for the why, let me show you two code samples doing the same thing, one in c and the other in java.
In C

Code: Select all

typedef struct {
DbResultsHighLevelSpecific* results;
DbException* exception;
typedef struct {
DbResultsIntermediate1Specific* results;
DbException* exception;
typedef struct {
DbResultsIntermediate2Specific* results;
DbException* exception;
//repeat
typedef struct {
DbResultsIntermediateNSpecific* results;
DbException* exception;

//prep
//happy path
} else {
//error handling based on specifics of resultsBroad.exception
}
}

//other stuff

//happy path stuff
if(other.exception == 0) {
//happy path, result.results is now in a consistent state
} else {
result.exception =  other.exception;
}
} else {
}
return result;

}

//same thing as last method, just using DbResultsIntermediate2
}

int errorCode = checkDBstate();

if(errorCode ==0) {
LowLevelSpecific specific= getLowLevelStuff(specific,args)
//happpy path, result.results is now in a consitent state
} else {
result.exception  = describeProblem(errorCode, args,"stuff specifying context");
}

return result;
}
In Java:

Code: Select all

//prep
try {
DbResultsHighLevelSpecific thing = getHighLevelStuff();
//happy path
} catch (DbException e) {
//error handling based on e
}
}

public DbResultsHighLevelSpecific getHighLevelStuff() throws DbException {
DbResultsHighLevelSpecific result = new DbResultsHighLevelSpecific();

DbResultsIntermediate1Specific stuffWeActuallyWant = getIntermediate1();

//happy path stuff
OtherKindOfResultsSpecific other = getOtherStuff();
//happy path, result is now in a consistent state
return result;
}

public DbResultsIntermediate1Specific getIntermediate1() throws DbException  {
//same thing as last method, just using DbResultsIntermediate2
}

public DbResultsIntermediateNSpecific getIntermediateN() throws DbException  {
DbResultsIntermediateNSpecific result = new DbResultsIntermediateNSpecific();

int errorCode = checkDBstate();

if(errorCode ==0) {
LowLevelSpecific specific= getLowLevelStuff(specific,args)
//happpy path, result.results is now in a consistent state
} else {
throw new DbException(errorCode, args);//call stack is included automatically, so I don't bother specifying information on where
}

return result;
}
This style is very unusual for C, and for good reason. True exceptions are also possible in C, but the syntax is awkward, obscure, and vulnerable to infinite loops and memory leakages if done wrong.

The Java style is pretty standard. C# is very similar, and I think the only salient difference is that C# doesn't force you to declare potential exceptions in your method signatures.

I also made the simplification of having only checkDBstate determine if a DbException needs to be thrown. In reality it would be some like a beforehand check of the DB state, a check of the consistency of the LowLevelSpecific result, a check of the quality of the args, and a rethrowing of an exception coming up from the network layer.
The thing about recursion problems is that they tend to contain other recursion problems.

Wildcard
Candlestick!
Posts: 253
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

### Re: Coding: Fleeting Thoughts

Carlington wrote:<a graph-theoretic algorithmic question>

You may also want to ask on our sister thread. I don't know the answer offhand (though some have been offered already which sound good) but if I were facing such a problem, I would pull out my copy of "Introduction to Algorithms" and review the graph based algorithms discussed therein. Truly it's more of a CS question than strictly coding.
There's no such thing as a funny sig.

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

### Re: Coding: Fleeting Thoughts

Flumble wrote:A bi-directional search can help greatly in large graphs with long median shortest paths. But for graphs less than millions of nodes it shouldn't matter.

If you want to know the reachability of only a few nodes, you can use a breadth-first traversal of your directed graph (you don't need to actually copy it to such a structure, just traverse it like it is one); or if you somehow have a heuristic, A*.

If you want to know the reachability/distances of all nodes, take a look at Floyd-Warshall. Or, in case you want to know the reachability of nodes in an undirected graph, it's equivalent to graph coloring/finding components.

If you want to know the reachability of one node from all the others, it's also kind of like graph coloring.

Graph coloring is not equivalent / has nothing to do with finding components. Finding components is also not equivalent to reachability because you're not only interested in (strongly) connected components but also in the paths between them. However finding the (strongly) connected components would allow you to translate reachability to topological sorting. Reachability can be efficiently solved by depth-first search or by breath-first search, as you mentioned. I suspect that DFS performs slightly better than BFS for non-metric graphs as managing a stack is slightly easier than managing a queue.

Posts: 1419
Joined: Sat Mar 07, 2009 11:33 am UTC
Location: ᘝᓄᘈᖉᐣ
Contact:

### Re: Coding: Fleeting Thoughts

I've been thinking about a SciPy-related problem I can't quite figure out yet. Since my post on Stack Overflow didn't get any replies and none of my friends appear to have a solution either, I figure it can't hurt to ask here as well. Quoted from Stack Overflow:
Yours truly on Stack Overflow wrote:I have a large dataset of the form [t, y(t)] to which I want to apply an IIR low-pass filter (first- or second-order Butterworth should suffice) using scipy.signal (in particular scipy.filter.butter and scipy.filter.filtfilt). The problem is that t is not regularly spaced, which appears to be a requirement for the functions in scipy.signal.

For any "missing" points, I know that my signal remains unchanged from its previous value (so given two consecutive points t1 and t2 in my t-data and a point T not in the data, such that t1<T<t2, the "real" function Y(t) which I'm sampling would take the value Y(T)=Y(t1)). t is integer-valued, so I could simply add the missing points, but this would cause the size of my dataset to grow by a factor ~10, which is problematic given that it's already very large.

So the question is, is there a (sufficiently simple and low-overhead) way to filter my dataset without inserting all "missing" points?

ucim
Posts: 6892
Joined: Fri Sep 28, 2012 3:23 pm UTC

### Re: Coding: Fleeting Thoughts

Link wrote:So the question is, is there a (sufficiently simple and low-overhead) way to filter my dataset without inserting all "missing" points?
I don't know if you can get inside the functions (and I'm not familiar with these particular ones) to do this, but a recursive callback function for y(t) that would return

isset(y(t)) ? y(t) : y(t-1)

might do the trick. Then feed this into your dataset analysis functions. It essentially fills in the points on the fly.

Depending on how many points are missing, this could be altered to keep track of the last t that was set, and return that, Or, perhaps you could set up an array (i.e. called "oldindex") which, as each of its elements, has the next value of t whose value of y is set.
oldindex = array ((0,0), (1,12), (2,45), (3,141)...
and the function
getoldindex(x) which returns the highest index whose associated value is <= x
Then use the nonrecursive callback:

isset(y(t)) ? y(t) : y(getoldindex(t))

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Heartfelt thanks from addams and from me - you really made a difference.

phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

### Re: Coding: Fleeting Thoughts

I feel like you're going to need to fill in all the missing points eventually, anyway... like, say you had 100 points, irregularly spaced between 0 and 1000... then no matter what you do, after you run the filter, I'd expect you to have a dataset of 1000 points. So if expanding your input dataset to the full 1000 points by filling in all the in-between data and then running the filter inplace, would be too big to fit in memory, then you're going to have troubles.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

PM 2Ring
Posts: 3715
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

### Re: Coding: Fleeting Thoughts

Link wrote:I've been thinking about a SciPy-related problem I can't quite figure out yet. Since my post on Stack Overflow didn't get any replies and none of my friends appear to have a solution either, I figure it can't hurt to ask here as well.

Sorry, I didn't even look at your question earlier, since I don't know SciPy. There's a fairly simple & efficient solution using bisection to interpolate missing values. I've posted an answer on SO; I hope you like it.

Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

### Re: Coding: Fleeting Thoughts

I have posted an answer too, which is a bit more efficient.
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

Posts: 1419
Joined: Sat Mar 07, 2009 11:33 am UTC
Location: ᘝᓄᘈᖉᐣ
Contact:

### Re: Coding: Fleeting Thoughts

Cheers! I'll have a look when I get the time (tomorrow, hopefully).

phlip wrote:I feel like you're going to need to fill in all the missing points eventually, anyway... like, say you had 100 points, irregularly spaced between 0 and 1000... then no matter what you do, after you run the filter, I'd expect you to have a dataset of 1000 points. So if expanding your input dataset to the full 1000 points by filling in all the in-between data and then running the filter inplace, would be too big to fit in memory, then you're going to have troubles.
Yeah, that's something I thought of only after I posted the question, too. I guess the alternative would be to memory-map it, but that's going to be even slower than this already is. Guess I'll just have to see how far I can pre-trim the data without losing too much information. If it doesn't work, I guess I'll have to look at a different option. Maybe somehow "stream" the data through the filter and chuck out points from the output on the fly... but that sounds horrid as well. Ack, getting carried away again!

Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: Coding: Fleeting Thoughts

Or, instead of the points, get the frequency components. Or, instead of the frewuency components, get a sampling of points sufficient to reproducr the frequency components?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

PM 2Ring
Posts: 3715
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

### Re: Coding: Fleeting Thoughts

Jplus wrote:I have posted an answer too, which is a bit more efficient.

Nice approach, Julian. I didn't think of doing it like that, but I guess it works if the filtering algorithm accepts an iterator and doesn't need random access or multiple passes over the data.

Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

### Re: Coding: Fleeting Thoughts

Even if it does need multiple passes, you can save the output of the generator to a list and still avoid a log factor on the running time.
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)