Coding: Fleeting Thoughts

[Xeio]

Lies! MM is months, mm is minutes.

[phlip]

+%Y%m%d-%H%M%S

[Rysto]

The other is to use macro hackery. If you define your implementation in a header file, you can arrange things so that something like

Code: Select all

#define HEAP_DATA_TYPE double
#include "my_heap.h"

(I suggest actually undefining HEAP_DATA_TYPE in my_heap.h, but that's personal preference. There is a reason though -- it seems like it would reduce the risk of including my_heap.h with the wrong type.)

I think the latter option sucks less, but that's me. (It means that merely the implementation of your heap is terrible, whereas with a void* interface, the use of it is as well.)

Lame. This is how you implement a type-safe, generic data structure in C.

[EvanED]

The other is to use macro hackery. If you define your implementation in a header file, you can arrange things so that something like

Code: Select all

#define HEAP_DATA_TYPE double
#include "my_heap.h"

(I suggest actually undefining HEAP_DATA_TYPE in my_heap.h, but that's personal preference. There is a reason though -- it seems like it would reduce the risk of including my_heap.h with the wrong type.)

I think the latter option sucks less, but that's me. (It means that merely the implementation of your heap is terrible, whereas with a void* interface, the use of it is as well.)

Lame. This is how you implement a type-safe, generic data structure in C.

Ugh, having worked on code that used macros like that (and having worked on the macros themselves), my way is way better.

Using macros like that is horrendous on several different levels.

[phlip]

OK, that's possibly one of the worse bugs I've had.

A while ago, when I set up Cygwin on my Windows boot, I found that it didn't come with a "killall" utility... just the usual "kill" that works by PID. So I built my own bare-bones killall using kill and pidof. Except that Cygwin didn't have pidof, either, so I built my own bare-bones one using which, ps and grep.

The things I learned, using this script today:

• "set -e" is my friend, and I should use it more often in these small scripts (where I don't intend to do proper error handling).
• If I pass a non-existant program to my hacked pidof, a bug caused by cascading errors (that set -e would catch) results in it returning the PID of every active process.

[headprogrammingczar]

I think the moral of that story is "you should be running a virtual linux OS instead"...

[EvanED]

Also: never run killall on a SunOS box.

[maafy6]

Also: never run a SunOS box.

FTFY

Granted, I probably have an irrational hatred of SunOS thanks to being forced to work on a system on Solaris 8 at work. So happy with that.

So very happy.

[rath358]

Thought of a maybe slightly better than brute force way to do that huge find the highest possible sum path through the triangle problem from project Euler. A shame I have real-world things like finals to worry about...

[RoadieRich]

Thought of a maybe slightly better than brute force way to do that huge find the highest possible sum path through the triangle problem from project Euler. A shame I have real-world things like finals to worry about...

There is a very neat method to solve that one. Gives you a runtime of O(n^2), where n is the number of rows. Brute force is closer to O(n!), I think.

[phlip]

Brute force is closer to O(n!), I think.

Not quite that bad... O(n2ⁿ) I think: there's 2ⁿ paths to check, and each one involves adding up n numbers.

[Thesh]

It should be O(n2^n-1). There's two choices each step down, but no choice for the first row.

[phlip]

That's only different by a factor of 2, though, and big-O notation ignores those...

[Shivahn]

Thought of a maybe slightly better than brute force way to do that huge find the highest possible sum path through the triangle problem from project Euler. A shame I have real-world things like finals to worry about...

There is a very neat method to solve that one. Gives you a runtime of O(n^2), where n is the number of rows. Brute force is closer to O(n!), I think.

I felt so satisfied when I figured that one out.

[Dason]

Thought of a maybe slightly better than brute force way to do that huge find the highest possible sum path through the triangle problem from project Euler. A shame I have real-world things like finals to worry about...

There is a very neat method to solve that one. Gives you a runtime of O(n^2), where n is the number of rows. Brute force is closer to O(n!), I think.

I hadn't put too much thought into this particular problem for quite some time but your comment here helped me figure out a solution. Thanks!

[troyp]

It should be O(n2^n-1). There's two choices each step down, but no choice for the first row.

That's actually the same thing ;-)

[tastelikecoke]

Freshie CS student here. What do you think would be a good example of a real life CS problem? I just want an idea on what you would call a practical problem, and probably try solving it

[joshz]

Traveling salesman has enormous practical applications and implications

So does prime factorization---it's essential for cryptography.

[RoadieRich]

Freshie CS student here. What do you think would be a good example of a real life CS problem? I just want an idea on what you would call a practical problem, and probably try solving it

Anything that uses a datastore of some sort is applicable: do you want fast random access or sequential access, fast inserts, ultra efficient use of memory? That's tree vs list vs array.

For instance, how do you store an index of a library's books, if they're usually looked up by author? (Yes, letting a database handle it for you is the proper answer, but that's soft eng, not comp sci.)

It depends on how deep you want to go. I'm guessing "Freshie" means you've just started?

[tastelikecoke]

It depends on how deep you want to go. I'm guessing "Freshie" means you've just started?

Yep, not completely zero though. I guess I should read more about data structures then.
But I'm more of wondering what do programmers actually do while working in some IT company, so actually my question's closer to soft eng.

[Steax]

Very practical challenge: Have a long list of items, in which you have to display with pagination and sorting options (bonus: fuzzy searching and filtering). And by long, I mean catching issues with your method of slicing arrays, and finding corner cases. And make it a real solution: collapse the pagination items if they go over a threshold, allow sorting across 2 properties (i.e. use objects instead of just strings). I find that this challenge trips up a lot of people.

I can give you a bunch of practical things a guy would do in the web development industry, if you want those.

[b.i.o]

One project I've worked on recently that's probably simple enough for you to actually implement (and possibly useful enough for you to actually use for yourself at some point) is a file archiving program. It takes files from a whole bunch of locations (my version had some remote ones, and some on the local file system), puts them into archive files (.tar.gz's/zips) and then copies those archives into some remote locations.

[Yakk]

I can give you a hard one.

A data structure for a table with the following properties:
1: You can get element n through element n+m fast (where m is small, and n can be large).
2: You can delete element n fast.
3: You can change how it is sorted in a stable manner. This needs to be reasonably fast, and more importantly responsive (ie, if it starts sorting what you are looking at first, that is good). You can sort on any of the columns. (note that stable sorting is important)
4: You can insert an element at location n fast.
5: You can insert an element to be placed in sorted order fast.
6: You need to be able to deal with millions or more elements at once in the structure, while only using a few megs of actual memory (at most).
7: You need to be able to deal with filtering (ie, only show elements that pass this test, or remove elements that fail this test), including asynchronous filtering.
8: You need to be able to change properties of the items in the columns fast (causing a resort of that item).

I think that is about it. It is a rough description of what you need for an inbox data structure that doesn't suck. Note that most inbox data structures suck.

The interesting part, why something like a standard C++ container doesn't work, is the ability to both get the nth element fast and delete it/add one fast. No standard library C++ container can do this, but it isn't hard to write.

My best stab at what I'd use for the above problem (I never got around to writing it) is a something like a B-tree with each tree knowing how many leaves it has under it.

[Xeio]

Next time, remember that your gut instincts are right, when you navigate to a function and the first line is the comment

Code: Select all

//Whamjacked!

Something terrible is afoot.

Ok, so "something terrible" is a null reference exception, and is a minor fix, but still...

[tes]

I'm learning Java, and it seems a bit wrong to me that you can't access private member variables of the parent class in a subclass. When I want to override a function using those member variables, how should I do it? From what I understand of encapsulation, these variables shouldn't be accessible outside the parent class and subclasses, so public get and set methods are not an option. When I use protected, all classes in the same package can access the variables.

[RoadieRich]

I'm learning Java, and it seems a bit wrong to me that you can't access private member variables of the parent class in a subclass. When I want to override a function using those member variables, how should I do it? From what I understand of encapsulation, these variables shouldn't be accessible outside the parent class and subclasses, so public get and set methods are not an option. When I use protected, all classes in the same package can access the variables.

Not allowing access to private members of parent classes seems pretty normal to me - it's the way C++ does it as well.

Use protected, and assume your programmers are consenting adults, a la python?

Alternatively, use more packages.

[EvanED]

Java protected doesn't act like C++ protected. (Regardless of inheritance relationships, Java protected only allows access to other classes in the same package.)

I think the way to look at this is that Java is protecting against actual deliberate, malicious attempts to access those semi-private variables. (This is important because a lot of important things like their security manager depend on the integrity of those variables!) And from that point of view, C++ protected variables might as well be public, because to some extent if you wanted to access one you could just make a subclass and do so. Whereas on the C++ side, they can't really protect against access at all, because you can do horrible-but-working stuff like #define private public or synthesizing pointers to the private members.

Edit: as pointed out below, my statements about the semantics of Java protected are wrong.

[tes]

Thanks, I'll use protected, then (and packages - until now, I had practically all my files in one package). I'm a beginner, so I didn't mean to say that Java was doing something wrong, just that it didn't seem very intuitive to me.

[You, sir, name?]

Java protected doesn't act like C++ protected. (Regardless of inheritance relationships, Java protected only allows access to other classes in the same package.)

I think the way to look at this is that Java is protecting against actual deliberate, malicious attempts to access those semi-private variables. (This is important because a lot of important things like their security manager depend on the integrity of those variables!) And from that point of view, C++ protected variables might as well be public, because to some extent if you wanted to access one you could just make a subclass and do so. Whereas on the C++ side, they can't really protect against access at all, because you can do horrible-but-working stuff like #define private public or synthesizing pointers to the private members.

In C++, you'd use pimpl'ing if you wanted to truly hide implementation details from a public interface.

[RoadieRich]

Java protected doesn't act like C++ protected. (Regardless of inheritance relationships, Java protected only allows access to other classes in the same package.)

I think the way to look at this is that Java is protecting against actual deliberate, malicious attempts to access those semi-private variables. (This is important because a lot of important things like their security manager depend on the integrity of those variables!) And from that point of view, C++ protected variables might as well be public, because to some extent if you wanted to access one you could just make a subclass and do so. Whereas on the C++ side, they can't really protect against access at all, because you can do horrible-but-working stuff like #define private public or synthesizing pointers to the private members.

That's not what http://docs.oracle.com/javase/tutorial/ ... ntrol.html says:

The protected modifier specifies that the member can only be accessed within its own package (as with package-private) and, in addition, by a subclass of its class in another package.

[EvanED]

Wow, I totally didn't know that. Thanks for the correction.

I explicitly remember learning that what I said was true way back when (and in particular, contrasting Java and C++ and C#). I wonder if my brain just made that up whole cloth or if my source at the time was wrong. (Or if the semantics has changed, but that seems like by far the least likely of the three choices.)

[TheChewanater]

Stupidest mistake I've made in a while. I didn't notice this all day...

Code: Select all

CameraAnimator::CameraAnimator(SceneNode* cameraNode,
                               btDynamicsWorld* world,
                               BaseApplication* application,
                               float movementSpeed, float turningSpeed,
                               InputMethod inputMethod):
  mCameraNode(cameraNode),
  mWorld(world),
  mApplication(mApplication), 

[darkspork]

It is utterly pointless to try to arrange your Java code into folders or "packages" when you have cyclical dependencies. It just doesn't work.

I was trying to clean up my code, but there's only one class that nothing depends on, three classes that don't depend on anything (generated by Javacc) and the other thirty or so classes all pretty much depend on the same two classes which, in turn, depend on a class that depends on those thirty or so classes.

[RoadieRich]

If I want a thread to pause its processing loop, with the option of resuming it on an external event, which of the many c# thread control classes is most appropriate? I wanted to use Thread.suspend() and Thread.Resume(), but they're raising empty exceptions (as in no message at all), and a look at the docs shows them as deprecated.

(It's for a threaded software pwm on a netduino, and when the output is 0 or 100%, I want to stop the Write/sleep cycle.)

[TheChewanater]

FT: this is really awesome.

[Yakk]

If I want a thread to pause its processing loop, with the option of resuming it on an external event, which of the many c# thread control classes is most appropriate? I wanted to use Thread.suspend() and Thread.Resume(), but they're raising empty exceptions (as in no message at all), and a look at the docs shows them as deprecated.

(It's for a threaded software pwm on a netduino, and when the output is 0 or 100%, I want to stop the Write/sleep cycle.)

Multithreaded logic is rarely as simple as you are describing. It is not just what you want, but the details, that really matter.

The simplest pattern you might want to think about is the multi threaded consumer-producer queue pattern.

Many threads can put tasks into the queue, and one thread eats tasks off the queue and does work based on it.

Now, this doesn't exactly match your vague description of your problem, but it might match your actual problem sufficiently well. And when working in multi-threaded programming with a skill level that doesn't already know why suspend and resume are deprecated, you really really want to use a pattern that someone else has worked the bugs out of, and not come up with something new.

Is the multithreaded consumer-producer (one-many) queue sufficient for your problem? If so, you could google an implementation, or I could sketch one.

(The way you'd do this in your case might be to have small sized tasks that you consume in the write cycle. When you hit 100%, you stop producing these small sized tasks, until it falls. There is some control-theoretic problems whereby hit would oscillate out of control, but hey...)

[RoadieRich]

The scenario is this: I have a digital output that I want to be able to fade in and out, according to events triggered by other code. Currently, my (untested, due to previous problem) code has a thread running "while (true) {write(on); sleep(brightness); write(off); sleep(100-brightness);" (Pseudocode, obviously), with brightness (a percentage value) altered by the event handlers. I want to stop the while loop from thrashing needlessly when brightness is 0 or 100. Should I just run the while loop on that condition, and restart it when needed?

[Thesh]

Yes, your while loop should just loop on that condition. To prevent it from running twice if someone clicks twice, you can use a mutex.

[RoadieRich]

Ok, I've re-written, and it compiles and runs, but it's just spawning hundreds of threads (once each time Write() is called - _t.IsAlive is always false). What have I done wrong?

Code: Select all

public class SoftwarePWM : OutputPort
{
   public SoftwarePWM(Cpu.Pin portID, bool initialState)
      : base(portID, initialState)
   { }

   private Thread _t;
   private int _b;

   public void Write(int brightness)
   {
      _t = new Thread(modulate);
      _b = brightness <= 100 ? brightness : 100;
      switch (_b)
      {
         case 0:
            base.Write(false);
            break;
         case 100:
            base.Write(true);
            break;
         default:
            if (!_t.IsAlive)
               _t.Start();
            break;
      }
   }
   private void modulate()
   {
      int i;
      while (_b >  0 && _b < 100)
      {
         base.Write(true);
         //for (i = 0; i < _b; i++) { }
         Thread.Sleep(_b);
         base.Write(false);
         //for (; i <= 100 - _b; i++) { }
         Thread.Sleep(100 - _b);
      }
   }
}

Edit: yes, I know from previous discussion that it's not really correct to inherit from OutputPort, but let's deal with that later. The basic skeleton was written before that.

[Xeio]

If you don't want a new thread to spawn every time you call write why do you keep calling new?

Needs something like

Code: Select all

 if (_t == null) _t = new Thread (modulate);

Also, unless you're trying to save memory or might not always call write, you could initialize in the variable declaration to save the null check.