|
hooah posted:
what's the question then?
|
#
?
Apr 25, 2015 17:31
|
|
I'm just the grader.
|
|
| # ? Jun 11, 2024 16:30 |
|
|
Well, on the assignment it's "A graph is k-colorable if each vertex can be given one of k colors, and no edge connects identically-colored vertices. Give a linear-time algorithm to test a graph for two-colorability. Assume graphs are stored in adjacency-list format; you must specify any additional data structures that are needed." However, half the class wrote an algorithm for 2-colorability, and the prof said that's fine.
|
|
#
?
Apr 25, 2015 17:34
|
|
|
Yeah okay, so you're not worried about weights at all, and input graphs might be cyclic. In that case a DFS/BFS algorithm that alternates marking 0 and 1 to each new node and checks the next node against the current mark to determine whether you're in an odd-cycle. Should still be O(V+E) JawKnee fucked around with this message at 18:22 on Apr 25, 2015 |
|
#
?
Apr 25, 2015 18:14
|
|
|
hooah posted:I'm trying to figure out if students' algorithms for 2-coloring a graph are linear time. Most of them do something like BFS or DFS, but most don't mark nodes as visited. Here's an example: I was going to complain that this is wrong since it doesn't actually check the last vertex, but then I realized the last vertex would have been checked against whatever it was connected to anyway. I guess it could miss on graphs where there's a vertex connected to itself.
|
|
#
?
Apr 25, 2015 19:19
|
|
|
HappyHippo posted:I was going to complain that this is wrong since it doesn't actually check the last vertex, but then I realized the last vertex would have been checked against whatever it was connected to anyway. I guess it could miss on graphs where there's a vertex connected to itself. Usually when you see coloring algorithms they explicitly say something like "let G=(V,E) be an undirected graph with no reflexive edges", that's a typical assumption about the input. Mostly because such a graph is completely uncolorable.
|
|
#
?
Apr 25, 2015 19:51
|
|
|
Jsor posted:Usually when you see coloring algorithms they explicitly say something like "let G=(V,E) be an undirected graph with no reflexive edges", that's a typical assumption about the input. Mostly because such a graph is completely uncolorable. Yeah I kinda figured they wouldn't put a graph like that in. It's kinda a bug that isn't a bug - whoever wrote it probably didn't intend to miss the last vertex, but for this particular problem it turns out that it doesn't actually matter. Still, the grader might want to notify the student so they're more careful in the future.
|
|
#
?
Apr 25, 2015 20:37
|
|
|
I'm trying out go and I do not understand how the type system works. Can someone explain to me why withForward and withUpdateOutput don't produce the same output, and what I need to do to Forward to make it so that they do?code:
|
|
#
?
Apr 25, 2015 21:42
|
|
|
Get rid of the GenericModule type altogether, it's pointless and stupid. Objects don't have vtables. A value of interface type consists of a tuple, one field of which is the value (or a pointer to it or something), the other field of which is the name of the type (essentially). The function Forward just calls self.UpdateOutput(3) where self is a *GenericModule, and there's nothing having to do with Linear there. Linear just has a field of type GenericModule, that's all. Method name resolution just implicitly accesses the unnamed field if there is one (and if the method name otherwise would not resolve?). sarehu fucked around with this message at 22:22 on Apr 25, 2015 |
|
#
?
Apr 25, 2015 22:18
|
|
|
That will make the example work, but what I really want is to have a bunch of different types of module that each UpdateOutput in their own way. I also want every module to have a Forward function that that first does some other stuff that's the same for all modules and then calls UpdateOutput, but I only want to write Forward once.
|
|
#
?
Apr 25, 2015 23:20
|
|
|
Flip it around. Embed the specific type in the general type. You can embed an interface type in a struct types, so you can define an interface that covers all your Forwarder needs and embed that in your GenericModule struct.
|
|
#
?
Apr 25, 2015 23:49
|
|
|
Nippashish posted:That will make the example work, but what I really want is to have a bunch of different types of module that each UpdateOutput in their own way. I also want every module to have a Forward function that that first does some other stuff that's the same for all modules and then calls UpdateOutput, but I only want to write Forward once. Make Forward not be part of the interface, have it take an argument of type Module. (Just like you should in C#, Java, C++, etc.)
|
|
#
?
Apr 26, 2015 00:01
|
|
|
I'd like to make a program where I'd mostly be making my own flash-card kind of system for improving my memory in general and on specific topics, maybe have a general option where the program selects random words/numbers for me to remember, as well as flash-cards sets tailored to said specific subjects. At least that's the basic premise. It sounds a bit weird to go to such specifics here but I basically wanted to show that I'm just wanting to make a (hopefully) simple program along those kind of lines. I've tried a few times to learn a programming language (usually C or C++) but I've decided I should just go for whatever the simplest thing is where I can just start making something like the above straight off the bat. Or close to it. What would people recommend? I'd mostly be wanting it for my windows computer, and mostly just for this type of program at the moment, but if the same language could be used to bring it to my android phone or linux netbook, or if it can scale up well to more advanced projects then that would be great too, but I'm mainly hoping for simplicity and a short start-up time. I've hopefully not left out any important details, I really am new to the whole programming business. Thanks for any tips!
|
|
#
?
Apr 26, 2015 01:08
|
|
|
If you want to do this to learn programming, that's totally cool. But if your end product is the goal, just use Anki. Not only are they flash cards, but it also does spaced repetition which generally improves retention rates much better than the uniformly random shuffle selection your program probably would do.
|
|
#
?
Apr 26, 2015 01:16
|
|
|
sarehu posted:Make Forward not be part of the interface, have it take an argument of type Module. (Just like you should in C#, Java, C++, etc.) If I do this I need to call Forward like Forward(linear, 3) and UpdateOutput like linear.UpdateOutput(3) which is confusing because now the call site needs to care if it's calling something specific to linear directly or something generic that is implemented in terms of things that are specific to linear. If this were C++ I'd have a Module class that defines Forward and declares a pure virtual UpdateOutput and a Linear class that inherits from Module and defines UpdateOutput. Lonely Wolf posted:Flip it around. I'm not understanding how to set this up. Everything I've tried involves a lot of boilerplate and doesn't compile so I'm clearly going about it the wrong way.
|
|
#
?
Apr 26, 2015 01:55
|
|
|
Nippashish posted:If I do this I need to call Forward like Forward(linear, 3) and UpdateOutput like linear.UpdateOutput(3) which is confusing because now the call site needs to care if it's calling something specific to linear directly or something generic that is implemented in terms of things that are specific to linear. Making functions and passing parameters to them is something that you should be comfortable with. In fact, in terms of communicating information about what's really going on, it's superior. Nippashish posted:If this were C++ I'd have a Module class that defines Forward and declares a pure virtual UpdateOutput and a Linear class that inherits from Module and defines UpdateOutput. The way you would do something in C++ is first of all, irrelevant to how you'd do it in Go, and second of all, a silly thing to do in C++ too. (It's better to make it a function if it uses the public API than a non-virtual member function because that lowers the API surface area and makes the code more readable.) (That's just my opinion, but my opinion is right.)
|
|
#
?
Apr 26, 2015 02:36
|
|
|
It sounds like that's what you need to do but what you're trying to do is figure out to get inheritance working. Go does not have inheritance, it has type embedding. Embedding is composition. To explain my previous post better, however: https://play.golang.org/p/jOiR8XInOR That pattern is only really useful if you're doing more than just one thing to the embedded value, like a bunch of utility methods wrapping one or more common kernels of functionality that can be implemented different ways and you just want to treat the whole thing as a single type. It sounds like in your case you just need a Forward function that accepts a value of an appropriately defined interface, unless there's more going on and you just pared it down to ask the question.
|
|
#
?
Apr 26, 2015 03:20
|
|
|
Dinho Eledair posted:I'd like to make a program where I'd mostly be making my own flash-card kind of system for improving my memory in general and on specific topics, maybe have a general option where the program selects random words/numbers for me to remember, as well as flash-cards sets tailored to said specific subjects. At least that's the basic premise. It sounds a bit weird to go to such specifics here but I basically wanted to show that I'm just wanting to make a (hopefully) simple program along those kind of lines. Maybe give Processing a shot. (It's sold as an artsy-fartsy design thing, but that's more the community than the technology.)
|
|
#
?
Apr 26, 2015 05:23
|
|
|
I have a WD NAS which runs ash as the shell. Every time I SSH into it I want it to auto source .ash_profile in my home dir. How do I set that up? I'm assuming this isn't a device dependent config considering this is not a typical device. edit: Oh nm, it looks like the WD NAS SSH session creates a temp user dir which gets deleted when I log out. Guh. Shaocaholica fucked around with this message at 00:03 on Apr 27, 2015 |
|
#
?
Apr 26, 2015 22:38
|
|
|
I have a style question. In a program with modules and subroutines, how do you decide whether a particular variable is passed as an argument to a subroutine vs. imported from a module? Edit: In my mind, input variables and output variables should be arguments of subroutines, while "background" data or constants can be imported. But the difference between input variables and background data is fuzzy, so I was wondering if there was a style guide somewhere that elaborated on these considerations.
|
|
#
?
Apr 27, 2015 04:48
|
|
|
Grundulum posted:I have a style question. In a program with modules and subroutines, how do you decide whether a particular variable is passed as an argument to a subroutine vs. imported from a module? Globals ("imported from a module") are ok if they're constant, but using mutable ones is a generally considered a Bad Idea.
|
|
#
?
Apr 27, 2015 04:59
|
|
|
What he said. And by "constant" that means values determined at compile time.
|
|
#
?
Apr 27, 2015 05:01
|
|
|
Why is it considered a bad idea? What terms should I be searching for to do my own reading on this?
|
|
#
?
Apr 27, 2015 05:23
|
|
|
What is the simplest tool for running a background script in the CLI that automatically includes a file in the specified locations of an HTML file? I want to load the code for my CSS and JS files as generated by SASS and ES6 initially, and inline, meaning: HTML code:The projects I want to do this for are submodules, so I can’t just use something like Jekyll to build a _site.
|
|
#
?
Apr 27, 2015 08:49
|
|
|
Grundulum posted:Why is it considered a bad idea? What terms should I be searching for to do my own reading on this? Reentrancy and thread safety are two reasons. Modularity and reusability are others. Global or shared mutable state is still logically parameters to the function, they're just hidden from normal view. It makes the behavior of the program opaque and harder to understand.
|
|
#
?
Apr 27, 2015 10:37
|
|
|
Grundulum posted:Why is it considered a bad idea? What terms should I be searching for to do my own reading on this? It is extremely useful if you can see the following things at a function call site: - All the function's inputs. - All the function's outputs. - Anything else that could affect the function's behavior (i.e. inputs). That is what's necessary if you want to practically reason about a function's behavior. Otherwise, you need institutional knowledge, and that needs to be maintained as a codebase changes over time. Taking this principle to an extreme, a function should not be able to do anything that reads or modifies the state of the outside universe (like printing to stdout, getting the current time, opening network connections) except through parameters passed explicitly by its caller. This is, quite often, absolutely the right thing to do! But practically, the standard library doesn't work this way, and it depends on how serious the input/output involved would be, and how inconvenient it would be to pass the parameters. You'll see people use global variables, for example, when making their error logging infrastructure (because it's "write-only" so it won't be a source of confusion, and you'd have to pass a handle to it everywhere), or for having a global thread pool or event loop handler (because usually you just want exactly one of those, and you'd have to pass it everywhere). Likewise, reading the current time is sensible when constructing a log message, but it's often better to pass in the current time (that you read exactly once) as a parameter, so that everything has the same time value (otherwise it's easy to get logic errors if you assume that time.Now() doesn't cross certain thresholds from call to call). The use of global mutable state in these examples is for the purpose of having a sort of "service," so to speak, that is just generally "available," but one that doesn't change in nature for different function calls, and isn't used to parameterize function behavior. Often you'll need to pass these sort of things as parameters for the sake of writing unit tests. For example, if you have code that use the current time in important ways, you'll need unit tests that control what time it is, so you'll make some kind of interface CurrentTime { time_t Now(); } type and pass that in. (And while running in production, maybe you'd want to wrap the system call interface to assert that time never goes backwards.) (Also, with the global thread pool or event loop handler example, it's often quite useful to know that a function does not do anything involving threads or events -- that it just does a plain computation. I've made event loop/thread pools that didn't use globals before, and it was a nice experience.) A common noob mistake is to think that "a database connection" is something that should be global. A connection pool, maybe. But even then, likewise, it's often useful to be able to read that your code is -not- using the global connection pool -- thanks to the fact that it doesn't take a reference to it as a parameter. Usually a connection pool would be passed pretty shallowly (to the point where you get a database connection out of it and use that) so it wouldn't really make sense either. Generally speaking: passing parameters is less annoying than you'd think, and every time you see somebody young try to avoid it, it's usually a mistake. Even with non-global state. For example, one time I worked on a project that evaluated queries in an "environment," which meant that a lot of code was passing around an env_t *env parameter (a pointer in C++). A coworker decided it would be convenient if he didn't have to pass that everywhere, and put a field env_t *env; in some objects, so that he could call its methods without having to pass the env parameter from the outside through something. Naturally, eventually the code changes such that the env_t object gets destroyed and a new one gets created (when the client requests more data for the same query) and a bug happens. Putting a reference to an object as a field in another object, because it's "convenient" since you don't have to pass it through separately, is another classic mistake, and you'll see people do it with stuff like database connections and poo poo all the time. I've never seen this sort of practice not come back to bite people. It's usually better just to suck it up and pass it as a separate parameter.
|
|
#
?
Apr 27, 2015 14:20
|
|
|
Does anyone have any experience allowing video files that are encrypted on disk (HIPAA reasons) to be viewed over the internet in a "secure" manner? Just looking into the topic for the first time, and the amount of info (and number of acronyms!) is overwhelming. In a nutshell, here's what needs to happen: 1. Authenticated User sees list of video files, which are stored encrypted on Server. (no problem) 2. User clicks on link, and video file plays in browser, and nobody from the HIPAA police gets mad. (  )There seem to be a whole mess of options: using a "streaming" server solution (HLS / RTMP), sending the encrypted file over and letting the client decrypt and play, etc. If anyone has done this sort of thing and as any suggestions on what worked for them or good links, I would be very appreciative!
|
|
#
?
Apr 27, 2015 17:54
|
|
|
sarehu posted:It is extremely useful if you can see the following things at a function call site: Thanks for this, and all the rest.
|
|
#
?
Apr 28, 2015 02:21
|
|
|
Lumpy posted:Does anyone have any experience allowing video files that are encrypted on disk (HIPAA reasons) to be viewed over the internet in a "secure" manner? Just looking into the topic for the first time, and the amount of info (and number of acronyms!) is overwhelming. Your best bet is probably to just download the video over a secure connection and play it locally. Trying to secure a UDP stream is not going to be a bucket of good times.
|
|
#
?
Apr 28, 2015 03:43
|
|
|
Munkeymon posted:RabbitMQ, the project whats docs I linked to, is an independent service that you can configure to route messages in different ways including pub/sub and RPC patterns. Your testbench software could just sit idly listening for messages (subscriber) from your experiment (publisher) and the Rabbit server would handle routing. Thanks--I'm looking at this right now. It did not really occur to me I was asking about a distributed system instead of just something that was generally asynchronous. I wasn't looking for to writing an agent, so I'll see what this can do.
|
|
#
?
Apr 28, 2015 16:54
|
|
|
nielsm posted:- IPC and RPC will also be very different, if you need to do that consider whether you can rely on a 3rd party library to abstract it. I appear to need to do this, our current solution is to just send a data stream over tcp and have things on either end pack and unpack, but I think we're going to need more throughput.
|
|
#
?
Apr 29, 2015 01:45
|
|
|
fritz posted:I appear to need to do this, our current solution is to just send a data stream over tcp and have things on either end pack and unpack, but I think we're going to need more throughput. I think loopback tcp goes through named pipes internally on Windows but I may be wrong, I'm not a network person. Use shared memory if you need the best performance but named pipes will be sufficient in 99% of cases.
|
|
#
?
Apr 29, 2015 02:07
|
|
|
fritz posted:I appear to need to do this, our current solution is to just send a data stream over tcp and have things on either end pack and unpack, but I think we're going to need more throughput. If it's just large chunks of data, definitely look into shared memory. On Windows that's implemented as memory-mapped files backed by pagefile rather than a regular file, by calling CreateFileMapping with INVALID_HANDLE_VALUE for hFile, but then specifying lpName as a string. Multiple processes can then create handles to the same named file mapping. Broadcast and general message-based IPC on Windows is actually best handled by window messages, even for non-GUI programs. Window objects have thread affinity, so messages are always delivered to a window's owning thread and get handled on that. The main disadvantage of window messages is the limited data capacity. (Message number, target window, source window, Wparam, Lparam.)
|
|
#
?
Apr 29, 2015 10:55
|
|
|
nielsm posted:Broadcast and general message-based IPC on Windows is actually best handled by window messages, even for non-GUI programs. Window objects have thread affinity, so messages are always delivered to a window's owning thread and get handled on that. The main disadvantage of window messages is the limited data capacity. (Message number, target window, source window, Wparam, Lparam.) Eh, I'd advise against window messages. They're easy to use if you already have a window, yeah. But if you don't you need to add some weird boilerplate. The whole windowing system is a mess and for example window handles can't have ACLs like all the other objects (pipes, events, whatever). Also window messages can't cross a desktop boundary, so they're out if you need to send stuff between a normal program and a service. Named events are dead easy to use (CreateEvent/OpenEvent, SetEvent/WaitForSingleObject). Named pipes behave mostly like their Unix equivalent but allow for duplex communication.
|
|
#
?
Apr 29, 2015 13:14
|
|
|
omeg posted:Eh, I'd advise against window messages. They're easy to use if you already have a window, yeah. But if you don't you need to add some weird boilerplate. The whole windowing system is a mess and for example window handles can't have ACLs like all the other objects (pipes, events, whatever). Also window messages can't cross a desktop boundary, so they're out if you need to send stuff between a normal program and a service. Named events are dead easy to use (CreateEvent/OpenEvent, SetEvent/WaitForSingleObject). Named pipes behave mostly like their Unix equivalent but allow for duplex communication. Ah, I had missed that named pipes on Windows do have a message-based mode. Use that instead then. Slightly odd that the client can elect to use a message-oriented pipe in byte-oriented mode, but whatever.
|
|
#
?
Apr 29, 2015 13:51
|
|
|
sarehu posted:It is extremely useful if you can see the following things at a function call site: Would you mind if I quoted this post in a blog? It's a great explanation (and I'd like to shout at people who think a global database connection is a great idea).
|
|
#
?
Apr 29, 2015 17:15
|
|
|
IT BEGINS posted:Would you mind if I quoted this post in a blog? It's a great explanation (and I'd like to shout at people who think a global database connection is a great idea). No problem. Edit: actually the last paragraph is job-specific, so I'd prefer if it were anonymized a bit, to use Env instead of env_t. sarehu fucked around with this message at 18:32 on Apr 29, 2015 |
|
#
?
Apr 29, 2015 18:26
|
|
|
Updating:Rocko Bonaparte posted:Thanks--I'm looking at this right now. It did not really occur to me I was asking about a distributed system instead of just something that was generally asynchronous. I wasn't looking for to writing an agent, so I'll see what this can do. I figured out from slogging through RabbitMQ that the hardest scenario I want to accomplish is very awkward to do in there, if I can do it at all. I guess what I wanted was a broker to manage scatter-gather for me. However, my requirements are so particular that it looks like I should probably retreat to writing my own broker using zeromq. I did not want to do that, but I think I got the street smarts for it now. My requirements for scalability, performance, and stability are actually not that great; we're talking a few signals in a minute. Well, at least for now.
|
|
#
?
Apr 29, 2015 21:10
|
|
|
sarehu posted:No problem. Cool, thanks. I'll anonymize it and PM you a link when it's up, in case you want to look it over.
|
|
#
?
Apr 29, 2015 21:39
|
|
|
I figured out I'd need multiple connections happening at once, but I need to be able to sit on an active connection in order to wait for responses. I did not want to have the broker open a connection in the reverse direction. So it looks like zeromq is out too. At this point, I was looking at raw sockets, but I find they are a real pain to use in Python. What about Twisted? I'm trying that now, and it superficially looks like I can scrape something together with it. I'm kind of wondering how well coroutines can handle keeping a connection open while the brokerage service aggregates responses.
|
|
#
?
Apr 30, 2015 01:01
|
|
|
|
| # ? Jun 11, 2024 16:30 |
|
|
Rocko Bonaparte posted:I figured out I'd need multiple connections happening at once, but I need to be able to sit on an active connection in order to wait for responses. I did not want to have the broker open a connection in the reverse direction. So it looks like zeromq is out too. You're in the realm of not knowing what you actually want. Here was what I believe is your original request: Rocko Bonaparte posted:I think I'm looking for something like a distributed publish/subscribe framework that works well in Python, but could also cooperate with C, C#, and Java. I mean, I might be wrong. This is not a problem you can shake a stick at (or a technology such as Redis, RabbitMQ, etc.) and get results. You need to architect a solution that extracts the commonalities between the domain problems, abstracts the differentiating functionality, provides state to the process and manages concurrency, etc. You will likely need a number of technologies, both 3rd party and in-house, in order to meet all criteria. You will need to try to keep in mind at all times the unknowable future, and to keep your code light and transportable to new use cases. You will need to be a software engineer, architect, product owner and manager. Or you can hack together whatever and leave it for the next guy.
|
|
#
?
Apr 30, 2015 04:57
|
|
