Ask General Programming Questions Not Worth Their Own Thread

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Ask General Programming Questions Not Worth Their Own Thread

«‹›671 »

ndb: Aug 25, 2005

Avenging Dentist posted:

When you doubleclick a file it just executes the command specified in the "open" verb for the extension.

Right, that's simple enough. Thanks everyone!

# ? Dec 19, 2008 14:59

Adbot: ADBOT LOVES YOU

# ? May 14, 2024 10:09

CIAduck: Apr 23, 2004

Quick FORTRAN question.
I'm not sure if this is worth its own thread or not, but here goes.

I have the following code:

quote:

logical function hasprereq (intclass, prereq)
implicit none

integer, intent(in) :: intclass, prereq
integer i, j

!Initially will return false
hasprereq = .false.

!Iterate through the listing matrix
!If a prereq is found, function return is set to true
do i = 0, row, 1
if (listing(i,0) == intclass) then
do j = 0, col, 1
if (listing(i,j) == prereq) then
hasprereq = .true.
end if
end do
end if
end do
end function hasprereq

(Sorry for the mess, I couldn't preserve the tabbing.)

The part in bold is my question. Can I set the return and have the function continue to run, or will it halt execution when I set the return value?

EDIT: I solved my problem. The recursion shown above doesn't work and the RECURSIVE keyword needs to be used as well as a RESULT variable. Proper syntax would look like this:
RECURSIVE LOGICAL FUNCTION hasprereq(intclass, prereq) RESULT(return)

CIAduck fucked around with this message at 06:51 on Dec 20, 2008

# ? Dec 19, 2008 23:22

POKEMAN SAM: Jul 8, 2004

Are there any good (free) native Windows profilers that will tell me why my application is page faulting out the rear end? I have millions of page faults after a couple of minutes. I have 4GB of RAM, and not even half of that is being used right now, and the application itself is only using 60MB of RAM.

Ugh.

# ? Dec 20, 2008 01:34

DLCinferno: Feb 22, 2003; Happy

Ugg boots posted:

Are there any good (free) native Windows profilers that will tell me why my application is page faulting out the rear end? I have millions of page faults after a couple of minutes. I have 4GB of RAM, and not even half of that is being used right now, and the application itself is only using 60MB of RAM.

Ugh.

Does ProcMon help?

http://technet.microsoft.com/en-us/sysinternals/bb896645.aspx

# ? Dec 20, 2008 02:34

POKEMAN SAM: Jul 8, 2004

DLCinferno posted:

Does ProcMon help?

http://technet.microsoft.com/en-us/sysinternals/bb896645.aspx

Unfortunately it doesn't show any events after the process starts (and all of the modules load and stuff.)

# ? Dec 20, 2008 06:29

Nippashish: Nov 2, 2005; Let me see you dance!

rjmccall posted:

Ensign Expendable posted:
Could someone explain dynamic programming to me? I understand the whole concept of reusing previous calculations, and the "largest continuous sum in an array" example everyone seems to give makes sense, but none of the larger problems do.

Dynamic programming is very straightforward. First off, it only applies to problems where the solution to a problem can be expressed in terms of the solutions of slightly smaller problems. You then solve the problem "bottom up": resolve the smallest problems first, remember their answers, and then keep using those to answer the next-smallest problems. So the key is to find some way to state the solution to the whole problem in terms of the solutions to smaller problems.

To elaborate on this a bit, dynamic programming is something you can use when divide and conquer doesn't quite fit. That is, when you have a problem where the solution can be expressed recursively, but the subproblems that you need to solve are not independent.

Compare merge sort with a function that generates the nth fibonacci number. Merge sort on a list with n elements is defined in terms of merge sort on a list containing elements 1 to n/2 and a list containing elements n/2+1 to n, these two problems have no overlap. On the other hand fibonacci(n) is defined in terms of fibonacci(n-1) and fibonacci(n-2). Notice that fibonacci(n-1) is thus defined in terms of fibonacci(n-2) and fibonacci(n-3) and if you were to solve this recursively you would solve the same problem several times.

Recursion trees demonstrating the above:

code:

                               mergesort(1 to n)
                                /               \
              mergesort(1 to n/2)                mergesort(n/2+1 to n)
                /            \                       /                   \
mergesort(1 to n/4)  mergesort(n/4+1 to n/2)  mergesort(n/2+1 to 3n/4)  mergesort(3n/4+1 to n)

... and so on

code:

           fibonacci(n)
           /       \
 fibonacci(n-2)  fibonacci(n-1)
   /  \           /       \
          fibonacci(n-3)  fibonacci(n-2)

... and so on

Notice how fibonacci(n-2) is repeated in different branches of the recursion whereas subproblems never repeat in mergesort. Because of the repeating subproblems finding the nth fibonacci number recursively requires exponential time. Dynamic programming is a technique to take a problem of this form and solve it in polynomial time. (This is pretty trivial to do for fibonacci numbers, but dynamic programming works on problems of this form in general). With dynamic programming instead of solving each subproblem every time you need it you solve all possible subproblems preemptively and store the solutions for later when you need them.

The dynamic programming solution to finding the nth fibonacci number would be something like:

code:

Algorithm fibonacci(n)
  Input: An integer n.
  Output: The nth fibonacci number.
Begin
  F <- An array of length n

  F[1] <- 1 // base cases for the recursion.
  F[2] <- 1

  for i = 3..n
    F[i] = F[i-1] + F[i-2] // notice this is pretty much the recursive definition,
                           // but we've already solved F[i-1] and F[i-2] so we just
                           // reuse the solutions we calculated before.

  return F[n]
End

Nippashish fucked around with this message at 08:02 on Dec 20, 2008

# ? Dec 20, 2008 08:00

hexadecimal: Nov 23, 2008; by Fragmaster

What you are describing there is more like memoization not dynamic programing itself. your formula doesn't change for Fibonacci numbers, but a lot of dynamic programing is for problems when you want to optimize some parameters, like the knap sack problem - http://en.wikipedia.org/wiki/Knapsack_problem.

Also consider longest increasing subsequence problem. You have some sequence S = { 5,4,7,3,10 } in which increasing subsequences are 4,7,10 or 5,7,10, etc. To calculate the length of the longest one you can make a new array M with same size as S where i'th element of M is the number of maximum length of increasing subsequences including i'th element of S. Now we can make recursive formula to give such maximum: M[i] = max(M[j]) + 1 where j > i and j < |S| and S[j]>S[i]. if no such j exist then M[i] = 1.

In this way, you can compute all elements of M and then compute maximum element of M to get largest increasing subsequence in S. You can use actual array M to memoize the results instead of having to recompute it for different elements. This greatly speeds up depth first search which is an easy way to implement the recursive formula.

There is a related problem called longest common subsequence that can be solved a bit differently and is also a good example of simple dynamic programing: http://en.wikipedia.org/wiki/Longest_common_subsequence

hexadecimal fucked around with this message at 08:53 on Dec 20, 2008

# ? Dec 20, 2008 08:36

floWenoL: Oct 23, 2002

hexadecimal posted:

What you are describing there is more like memoization not dynamic programing itself. your formula doesn't change for Fibonacci numbers, but a lot of dynamic programing is for problems when you want to optimize some parameters, like the knap sack problem - http://en.wikipedia.org/wiki/Knapsack_problem.

I have no idea what you're trying to say, but the important characteristics of a dynamic programming problem are just overlapping subproblems and optimal substructure, and frequently, memoizing the algorithm is equivalent to the normal bottom-up approach.

# ? Dec 20, 2008 08:55

hexadecimal: Nov 23, 2008; by Fragmaster

floWenoL posted:

I have no idea what you're trying to say, but the important characteristics of a dynamic programming problem are just overlapping subproblems and optimal substructure, and frequently memoizing the algorithm is equivalent to the normal bottom-up approach.

Well I just thought fibinacci numbers problem is not a very good problem to show for introduction to dynamic programing because it misses a lot of stuff that are involved in things like knaspack problem where you have to define optimal substructure using recursive formula. In Fibonacci numbers, the formula never changes, you just memoize it.

vvvvvvvvv and how is your reply any less shittier than mine?

hexadecimal fucked around with this message at 10:15 on Dec 20, 2008

# ? Dec 20, 2008 08:57

POKEMAN SAM: Jul 8, 2004

hexadecimal posted:

Well I just thought fibinacci numbers problem is not a very good problem to show for introduction to dynamic programing because it misses a lot of stuff that are involved in things like knaspack problem where you have to define optimal substructure using recursive formula. In Fibonacci numbers, the formula never changes, you just memoize it.

I love how you just got off probation yet you feel the need to start posting lovely answers right away.

# ? Dec 20, 2008 09:50

TSDK: Nov 24, 2003; I got a wooden uploading this one

Ugg boots posted:

Are there any good (free) native Windows profilers that will tell me why my application is page faulting out the rear end? I have millions of page faults after a couple of minutes. I have 4GB of RAM, and not even half of that is being used right now, and the application itself is only using 60MB of RAM.

Ugh.

I've had a quick flick through the MSDN, and it looks like you can get access to the pagefault counter at runtime by calling GetProcessMemoryInfo. So it should be relatively easy to whip up a little class that can be used to monitor the number of pagefaults generated at the function level. Scatter a few of these around at a high level, and then drill down into the child functions to find the hotspots.

# ? Dec 20, 2008 12:28

Emo.fm: Jan 2, 2007

Not sure if this warrants its own thread... I work for my college's radio station, and sadly our website is absolute poo poo. I have a lot of time on my hands right now so I thought a fun project for break would be to add a feature to our site that people have been asking for for a long time: dynamically updating playlists. I have basically no experience with web development whatsoever, but I am in my third year of a CS degree. I can write/edit HTML and CSS, and I think I'm a solidly intermediate Java programmer.

So what's the best way to go about this, and in what language? My basic idea is to have a login/out for the DJs, and a basic form that asks for song and artist (which the DJ would enter as they do their show... currently DJs have to fill out paper playlist records by hand), which is added to some kind of database/data structure type thing. The other people involved in the station (who know even less about this than I do) want me to set up an entire Wordpress-powered site just so people can post their playlists, which seems both boring (for me) and unnecessary, given what we actually want to do.

And finally, am I underestimating this project? I have about two weeks during which I can dedicate myself full time to this, plus another month or so before the semester starts to work part time on it.

# ? Dec 20, 2008 20:21

DLCinferno: Feb 22, 2003; Happy

Emo.fm posted:

Not sure if this warrants its own thread... I work for my college's radio station, and sadly our website is absolute poo poo. I have a lot of time on my hands right now so I thought a fun project for break would be to add a feature to our site that people have been asking for for a long time: dynamically updating playlists. I have basically no experience with web development whatsoever, but I am in my third year of a CS degree. I can write/edit HTML and CSS, and I think I'm a solidly intermediate Java programmer.

So what's the best way to go about this, and in what language? My basic idea is to have a login/out for the DJs, and a basic form that asks for song and artist (which the DJ would enter as they do their show... currently DJs have to fill out paper playlist records by hand), which is added to some kind of database/data structure type thing. The other people involved in the station (who know even less about this than I do) want me to set up an entire Wordpress-powered site just so people can post their playlists, which seems both boring (for me) and unnecessary, given what we actually want to do.

And finally, am I underestimating this project? I have about two weeks during which I can dedicate myself full time to this, plus another month or so before the semester starts to work part time on it.

This should be really easy, you basically have already outlined what you'll need.

- database
- login page
- playlist entry
- playlist view

PHP is pretty good language for a first-timer to get their feet wet, although lots of people will argue that it teaches you bad habits, but it sounds like you already has a solid enough programming base. If you do go with PHP you'll probably use mySQL as the database backend. Most web hosts give you some sort of GUI to manage your mySQL databases.

This is the perfect starting project in my opinion...and two full weeks plus some cleanup time should be enough to get it done and maybe add some additional stuff like playlist history, statistics on songs played, etc. Once you get the basics of connecting to a database and retrieving data down, you can easily do it for other stuff.

# ? Dec 20, 2008 21:28

yippee cahier: Mar 28, 2005

Emo.fm posted:

A wordpress plugin to handle the dynamic playlist stuff might be a good project. The station audience could probably be best served by a community oriented site. DJ blogs, an upcoming events calendar, record reviews, etc., could make it a pretty awesome site for the local music scene, your DJs and journalism students.

You'd have to work within someone else's API which might be a good challenge. You'd also have experience with a very popular content management system that has name recognition with nontechnical people.

# ? Dec 20, 2008 21:38

Emo.fm: Jan 2, 2007

sund posted:

A wordpress plugin to handle the dynamic playlist stuff might be a good project. The station audience could probably be best served by a community oriented site. DJ blogs, an upcoming events calendar, record reviews, etc., could make it a pretty awesome site for the local music scene, your DJs and journalism students.

You'd have to work within someone else's API which might be a good challenge. You'd also have experience with a very popular content management system that has name recognition with nontechnical people.

I didn't want to get into the drama of this too much, but I'm extremely opposed to this approach in this case. It's a very small college and an even smaller radio station, with barely enough manpower to support the radio itself. We maintain the website because "everyone should have a website!", and my goal is to implement the playlist-ing online as a cool feature for our listeners but also so that we can get away from the system of paper playlist-ing. Thanks for the suggestion, though.

DLCInferno, thanks for the response. Sorry if this is a ridiculous question (I know very little about PHP), but could this be implemented without a database? I know the data has to be stored in some manner, but our host is the college, which does not allow student groups to use mySQL, or any kind of databases in that sense, to my knowledge. I was hoping that since we're talking about relatively small and simple datasets, it would be possible to use something more rudimentary.

# ? Dec 20, 2008 21:51

DLCinferno: Feb 22, 2003; Happy

Emo.fm posted:

DLCInferno, thanks for the response. Sorry if this is a ridiculous question (I know very little about PHP), but could this be implemented without a database? I know the data has to be stored in some manner, but our host is the college, which does not allow student groups to use mySQL, or any kind of databases in that sense, to my knowledge. I was hoping that since we're talking about relatively small and simple datasets, it would be possible to use something more rudimentary.

Assuming you can write to the file system, then yes, you could certainly store the lists in XML or even raw text or something like that. But that's boring and not very robust and it doesn't give you the database experience!

Since you are limited with your hosting, maybe you can tell us what they do provide? If they are a Microsoft shop your only option might be ASP.NET for example. Honestly, I would be surprised that even a small college wouldn't happily give you a database somewhere - it would be tiny. If they have the extensions installed you could even use SQLite and do all the db stuff yourself.

Anyways, I think wordpress requires a database? Just tell them you are going to explore setting up wordpress and then use the database for your own site.

# ? Dec 20, 2008 22:03

Nippashish: Nov 2, 2005; Let me see you dance!

hexadecimal posted:

What you are describing there is more like memoization not dynamic programing itself. your formula doesn't change for Fibonacci numbers, but a lot of dynamic programing is for problems when you want to optimize some parameters, like the knap sack problem - http://en.wikipedia.org/wiki/Knapsack_problem.

Admittedly I have not studied memoization specifically, but the wikipedia page gives me the impression that memoization is about storing values from previous function calls to optimize future calls, which seems closely related to dynamic programming but is not really what I was describing.

# ? Dec 20, 2008 22:08

Emo.fm: Jan 2, 2007

DLCinferno posted:

...
Anyways, I think wordpress requires a database? Just tell them you are going to explore setting up wordpress and then use the database for your own site.

Good point. One other group on the campus server maintains a wordpress so I just emailed their guys to ask how they managed to get a mySQL set up. I think the issue has less to do with availability than demand... as far as I know, they're the only group that uses or had any desire for a database, so there's no established way of getting one set up besides chatting up the guys in IT. Which it appears I will be doing.

In the meantime, I guess I will start the process of actually learning PHP.

# ? Dec 20, 2008 22:19

hexadecimal: Nov 23, 2008; by Fragmaster

Nippashish posted:

Admittedly I have not studied memoization specifically, but the wikipedia page gives me the impression that memoization is about storing values from previous function calls to optimize future calls, which seems closely related to dynamic programming but is not really what I was describing.

Aha, but its not total picture. Memoization doesn't have to be storing results from recursive calls, you can use it in iterative methods just fine. It is just caching previous results so they don't have to be computed again. To use it effectively you have to define states and structure of your problem precisely, and then compute those states and use them for larger problem. This brings to the next point.

The heart of Dynamic programing is optimal substructure of a problem, that describes global solution in terms of previous solutions (or states), and few base cases. DP doesn't have to involve memoization at all, it just speeds it up. Once you have good formula, it also defines states for you, and this is when you can start using memoization to cache the states.

Look at my example in this page. I give definition for maximum increasing subsequence in terms of maximum subsequences starting with other elements. Only after I have such formula can I start thinking about how to memoize it. Also notice that I have base case for the formula.

hexadecimal fucked around with this message at 22:38 on Dec 20, 2008

# ? Dec 20, 2008 22:34

Ensign Expendable: Nov 11, 2008; Lager beer is proof that god loves us; Pillbug

Makes sense, thanks a lot. Now all I have to work on is the equation part.

# ? Dec 21, 2008 00:21

awesmoe: Nov 30, 2005; Pillbug

Has anyone got experience using qmake? I'm trying to figure out how to define additional targets for the generated makefiles - ie, `make` builds everything, but `make test` builds everything, generates an additional executable, and runs it. I don't want to specify it as a config argument to qmake when generating the makefiles from the .pro file, as I want it done at make time, not qmake time.
Is this possible?

# ? Dec 21, 2008 00:28

Nippashish: Nov 2, 2005; Let me see you dance!

hexadecimal posted:

Aha, but its not total picture. Memoization doesn't have to be storing results from recursive calls, you can use it in iterative methods just fine. It is just caching previous results so they don't have to be computed again. To use it effectively you have to define states and structure of your problem precisely, and then compute those states and use them for larger problem. This brings to the next point.

The heart of Dynamic programing is optimal substructure of a problem, that describes global solution in terms of previous solutions (or states), and few base cases. DP doesn't have to involve memoization at all, it just speeds it up. Once you have good formula, it also defines states for you, and this is when you can start using memoization to cache the states.

Look at my example in this page. I give definition for maximum increasing subsequence in terms of maximum subsequences starting with other elements. Only after I have such formula can I start thinking about how to memoize it. Also notice that I have base case for the formula.

Ahh ok. I learned about memoization and dynamic programming together (although we never mentioned memoization by that name) so I guess I missed the distinction. Thanks for clarifying.

# ? Dec 21, 2008 00:45

narbsy: Jun 2, 2007

Emo.fm posted:

If you can't get mySQL set up, use SQLite; if you're using PHP's PDO, you can write essentially the same SQL for mySQL as SQLite, with only small differences. It only requires a file per db. For smallish things it's reasonably speedy. Not to mention, it is far, far, far better than XML to store data.

# ? Dec 21, 2008 01:40

Emo.fm: Jan 2, 2007

narbsy posted:

If you can't get mySQL set up, use SQLite; if you're using PHP's PDO, you can write essentially the same SQL for mySQL as SQLite, with only small differences. It only requires a file per db. For smallish things it's reasonably speedy. Not to mention, it is far, far, far better than XML to store data.

Awesome! Thanks for the suggestion, this is perfect.

edit: Keeping in mind that I have very little control over/access to the server where the site is hosted... how can I tell if SQLite is installed? The standalone sqlite3 is working but none of the example php code I've found for interacting with an SQLite database will work (stuff like $db = sqlite_open('mysqlitedb');, for example).

Emo.fm fucked around with this message at 03:39 on Dec 21, 2008

# ? Dec 21, 2008 02:23

POKEMAN SAM: Jul 8, 2004

Ugg boots posted:

Are there any good (free) native Windows profilers that will tell me why my application is page faulting out the rear end? I have millions of page faults after a couple of minutes. I have 4GB of RAM, and not even half of that is being used right now, and the application itself is only using 60MB of RAM.

Ugh.

Interesting, every second I was constructing and deconstructing thousands of GDI+ Graphics objects (on the stack) and this was causing 10,000 page faults every second for some reason. Oh well, I was able to start reusing the same GDI+ Graphics object and now the page faults have gone away.

Edit: Welp, spoke too soon, looks like it works for one thread, though.

POKEMAN SAM fucked around with this message at 03:58 on Dec 21, 2008

# ? Dec 21, 2008 03:55

Jo: Jan 24, 2005; Soiled Meat

What is the best type of algorithm for generating a Delaunay Triangulation for a set of almost uniformly spaced points on a grid? Fortune's sweep line, still?

# ? Dec 21, 2008 04:30

TSDK: Nov 24, 2003; I got a wooden uploading this one

Ugg boots posted:

Interesting, every second I was constructing and deconstructing thousands of GDI+ Graphics objects (on the stack) and this was causing 10,000 page faults every second for some reason. Oh well, I was able to start reusing the same GDI+ Graphics object and now the page faults have gone away.

Edit: Welp, spoke too soon, looks like it works for one thread, though.

If the design of your program calls for the creation and destruction of quite a lot of small objects, you should consider enabling the low fragmentation heap settings. That should help keep the memory thrashing to a minimum.

Don't forget that even if you're creating an object on the stack, it may be making dynamic allocations internally that go through the heap.

# ? Dec 21, 2008 21:59

POKEMAN SAM: Jul 8, 2004

TSDK posted:

If the design of your program calls for the creation and destruction of quite a lot of small objects, you should consider enabling the low fragmentation heap settings. That should help keep the memory thrashing to a minimum.

Is this a flag on the binary or in the project settings?

TSDK posted:

Don't forget that even if you're creating an object on the stack, it may be making dynamic allocations internally that go through the heap.

Yeah, that wouldn't surprise me.

# ? Dec 22, 2008 00:21

TSDK: Nov 24, 2003; I got a wooden uploading this one

Ugg boots posted:

Is this a flag on the binary or in the project settings?

This'll do it:

code:

HANDLE process_heap = GetProcessHeap();
ULONG lfh = 2;
BOOL set_okay = HeapSetInformation( process_heap,
	HeapCompatibilityInformation,
	&lfh,
	sizeof( lfh ) );

# ? Dec 22, 2008 14:44

POKEMAN SAM: Jul 8, 2004

TSDK posted:

This'll do it:

code:

HANDLE process_heap = GetProcessHeap();
ULONG lfh = 2;
BOOL set_okay = HeapSetInformation( process_heap,
	HeapCompatibilityInformation,
	&lfh,
	sizeof( lfh ) );

Oh awesome, I'll try that out now!

# ? Dec 22, 2008 20:01

sonic bed head: Dec 18, 2003; this is naturual, baby!

Hopefully this is programmey enough, I definitely didn't think it deserved its own thread.

Does anyone know of any feature tracking webapp? Something like bugzilla but for features instead of bugs that runs somewhere else. I am tired of just keeping a list on a very commonly lost notepad and I would think that this type of service already exists somewhere.

# ? Dec 22, 2008 22:25

hexadecimal: Nov 23, 2008; by Fragmaster

sonic bed head posted:

Hopefully this is programmey enough, I definitely didn't think it deserved its own thread.

Does anyone know of any feature tracking webapp? Something like bugzilla but for features instead of bugs that runs somewhere else. I am tired of just keeping a list on a very commonly lost notepad and I would think that this type of service already exists somewhere.

I think mylyn for Eclipse does both features and bugs.

# ? Dec 22, 2008 22:54

tef: May 30, 2004; -> some l-system crap ->

launchpad ?

# ? Dec 23, 2008 03:37

wlievens: Nov 26, 2006

sonic bed head posted:

Hopefully this is programmey enough, I definitely didn't think it deserved its own thread.

Does anyone know of any feature tracking webapp? Something like bugzilla but for features instead of bugs that runs somewhere else. I am tired of just keeping a list on a very commonly lost notepad and I would think that this type of service already exists somewhere.

I track my feature requests in Trac along with my defects.

# ? Dec 23, 2008 12:10

syphon: Jan 1, 2001

Is there a way to dynamically load external libraries in VBScript? I don't know VBScript that well, so I'm not sure how to accomplish this.

I'm writing a script, and part of it needs to verify that a certain port is open on a remote server. All it does is check to see if the port is open, and returns success|fail from there. VBScript has no way to do this natively, but I found a DLL from this site that does this. I've tested it and it works fine.

Unfortunately, if the DLL isn't registered on the host machine, the script fails to compile. I picture this script running on any number of servers. This means i can't really package the DLL with it.

Is there any way to dynamically 'include' the DLL at script runtime? I'll have the DLL placed in the same location as the script (on a UNC share).

Is this possible?

# ? Dec 24, 2008 21:01

tripwire: Nov 19, 2004; _{ghost flow}

I'm making a simple python genetic algorithm for approximating images with 100 alpha blended triangles. The genome for each individual consists of 9*100 floats between 0 and 1; x and y for the three points in each triangle, and R G and B.

I'm using Cairo to draw it to a surface, but what I want to do is compare each pixel in this image to a pixel in the source image and sum up the RGB difference.

The (incomplete) code I've got so far is something like this http://pastebin.com/m663f2e45

Has anyone done this before? What do I want to do, write to a StringIO object? Whats the computationally fastest way to sum up the root mean square error between the source image and given image?

Any help is greatly appreciated.

tripwire fucked around with this message at 23:09 on Dec 28, 2008

# ? Dec 28, 2008 23:04

No Safe Word: Feb 26, 2005

tripwire posted:

Has anyone done this before? What do I want to do, write to a StringIO object? Whats the computationally fastest way to sum up the root mean square error between the source image and given image?

Any help is greatly appreciated.

http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/

This guy did it, and would be where I swore you got the inspiration to do it until you asked if anyone had done it before (especially since it's just a few weeks old). He includes code here as long as you grok C#.

# ? Dec 29, 2008 18:20

csammis: Aug 26, 2003; Mental Institution

No Safe Word posted:

http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/

This guy did it, and would be where I swore you got the inspiration to do it until you asked if anyone had done it before (especially since it's just a few weeks old). He includes code here as long as you grok C#.

Tripwire posted in this here thread so I think he's probably seen that first link before

I personally hadn't noticed the source code published, so thanks.

# ? Dec 30, 2008 16:53

tripwire: Nov 19, 2004; _{ghost flow}

I worked on a bit more but I think theres still a big program with my code, algorithm wise. It's really rough around the edges but I'm trying to pin down why its not working before I clean it up. Can anyone tell if they see any glaring mistakes with this code? It seems like the populations I make always converge very quickly and show almost no diversity after only a few generations. What am I doing wrong? Is the cairo surface not working properly? Is my code for reproduction obviously wrong in some way?

code:

import random, numpy, math
import cairo
import cProfile

class Triangle_genome(object):
    _id = 0
    def __init__(self, parent_id):
        """
        A triangle genome encodes a set of 100 triangles.
        Each Triangle is defined by 9 floats between 0 and 1,
        corresponding to the x1,y1,x2,y2,x3,y3,r,g, b,a """
        self._id = self.__get_new_id()
        self.fitness = None
        self._genes = [] #should be a list of 1000 floats
        self.parent_id = parent_id  #tracking the parents id should help with genealogy

    id    = property(lambda self: self._id)
    genes = property(lambda self: self._genes)

    @classmethod
    def __get_new_id(cls):
        cls._id += 1
        return cls._id

    @classmethod
    def create_new_genome(cls):
        """ Factory method for new triangle genomes """
        c = cls(0)
        for _ in xrange(1000):
            c._genes.append( random.random() )
        assert len(c._genes) == 1000
        return c
        
    def crossover(self,other):
        parent1 = self
        parent2 = other        
        child = self.__class__(self.id)
        if self.id == other.id:
            child._genes.extend(parent1.genes[::])
        else:
            child._inherit_genes(parent1,parent2)
        return child
        
    def _inherit_genes(child, parent1,parent2):
        for i in xrange(100):
            child._genes.extend(random.choice((parent1,parent2))._genes[i*10:i*10+10])
        
    
    def mutate(self):
        """ Mutates the genome """
        r = random.random
        for gene in self._genes:
            if r() < 0.04:
                gene += random.gauss(0,1)
                if gene > 1: gene = 1
                elif gene < 0: gene = 0
        self.fitness = None
        return self

    def __cmp__(self, other):
        """ Compares genomes by fitness """
        return cmp(self.fitness,other.fitness)

    def __str__(self):
        s = "Genes:"
        for gene in self._genes:
            s += '\n\t' + str(gene)
        return s


class Population(object):
    """ Manages a collection of individuals """
    evaluate = None
    
    def __init__(self):
        self.__pop_size = 100
        self.__create_population()
        self.__generation = -1
    
    def __create_population(self):
        self.__population = []
        for _ in xrange(self.__pop_size):
            g = Triangle_genome.create_new_genome()
            self.__population.append(g)

    def __repr__(self):
        s = "Population Size: %d" % self.__pop_size
        return s

    def __len__(self):
        return len(self.__population)

    def __iter__(self):
        return iter(self.__population)

    def __getitem__(self, key):
        return self.__population[key]

    def average_fitness(self):
        """ Returns the average raw fitness of population """
        sum = 0.0
        for c in self:
            sum += c.fitness

        return sum/len(self)

    def stdeviation(self):
        """ Returns the population standard deviation """
        # first compute the average
        u = self.average_fitness()
        error = 0.0        
        try:    # now compute the distance from average
            for c in self:
                error += (u - c.fitness)**2                 
        except OverflowError:
            #TODO: catch OverflowError: (34, 'Numerical result out of range')
            print "Overflow - printing population status"
            print "error = %f \t average = %f" %(error, u)
            print "Population fitness:"
            print [c.fitness for c in self]
        
        return math.sqrt(error/len(self))

    def reproduce(self):
        self.__population.sort()
        self.__population.reverse()
        survivors = self.__population[:int(round(self.__pop_size * 0.8))]
        spawn_amount = self.__pop_size - len(survivors)
        offspring = []
        offspring.extend([s.mutate() for s in survivors])
        while spawn_amount > 0:
            parent1,parent2 = random.choice(survivors),random.choice(survivors)
            if parent1.id != parent2.id:
                child = parent1.crossover(parent2)
            else:
                child = parent1.crossover(parent1) 
                
            child.mutate()               
            offspring.append(child)
            spawn_amount -= 1
#        print offspring, len(offspring)
        return offspring
    
    def evolve(self, n, termination_fitness):
        """ Runs a naive genetic algorithm for n generations,
        or until the termination fitness is reached, whichever comes first. """
        source_filename = 'mona.png'
        assert source_filename[-4:] == '.png', 'sorry only using png for the moment'
        source_surf = cairo.ImageSurface.create_from_png('Lenna.png')
        source_buffer = source_surf.get_data()        
        source_array = numpy.frombuffer(source_buffer, numpy.uint8)
        for _ in xrange(n):
            self.__generation += 1
            print '\n ******* Running generation %d ******* \n' % self.__generation
            self.evaluate(source_array)
            print 'Population\'s average fitness: %3.5f stdev: %3.5f' %(self.average_fitness(), self.stdeviation())
            #self.print_stats()
            best = max(self.__population)
            if best.fitness > termination_fitness: break
            new_population = self.reproduce()
            assert len(self) == len(new_population)
            self.__population = new_population  

    def evaluate(self,source_buffer):
        for individual in self.__population:
            if individual.fitness == None:
                individual.fitness = self.eval_genome(individual,source_buffer)      

    def eval_genome(self, individual, source_buffer):        
        WIDTH, HEIGHT = 256, 256
        surface = cairo.ImageSurface (cairo.FORMAT_ARGB32, WIDTH, HEIGHT)
        ctx = cairo.Context (surface)
        ctx.translate(0,0)
        ctx.scale(256,256)        
        #ctx.set_operator(cairo.OPERATOR_SOURCE)
        
        ctx.set_source_rgba(0,0,0,1)
        ctx.paint()
        for i in xrange(100):
            r,g,b,a = tuple( individual.genes[ i * 10 : i * 10 + 4 ] )
            x1,y1,x2,y2,x3,y3 = map(lambda q: q*3 - 1 ,tuple( individual.genes[ i * 10 + 4 : i * 10 + 10 ] ))
            ctx.set_source_rgba(r,g,b,a)
            ctx.move_to(x1,y1)
            ctx.line_to(x2,y2)
            ctx.line_to(x3,y3)
            ctx.close_path()
            ctx.fill()        
        if individual.id % 250 == 0: surface.write_to_png ('example' + str(individual.id) +'.png') # Output to PNG
        buf1 = surface.get_data()

        surface_array = numpy.frombuffer(buf1, numpy.uint8)
        assert numpy.alen(surface_array) == numpy.alen(source_buffer), 'Source image and Target image are different size!'
        rmse = (255 - math.sqrt(map(lambda x: x**2,numpy.diff(numpy.array( numpy.dstack((surface_array,source_buffer)), dtype=numpy.uint32 )))[0].sum())/255.0)
        #print 'genome %d has fitness of %f' % (individual.id,rmse)
        return rmse


pop = Population()
#pop.evolve(20000,0.9)
cProfile.run('pop.evolve(20000,0.9*255)')

tripwire fucked around with this message at 20:32 on Dec 31, 2008

# ? Dec 31, 2008 20:26

Adbot: ADBOT LOVES YOU

# ? May 14, 2024 10:09

tripwire: Nov 19, 2004; _{ghost flow}

Argh, what the hell is going on here?

This isnt the mona lisa

Only registered members can see post attachments!

# ? Dec 31, 2008 21:07

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Ask General Programming Questions Not Worth Their Own Thread

«‹›671 »