List is the primary collection type in C# and it's used for most things along with LINQ, there's usually not a good reason to use anything else. What are you trying to do?
-
Hey, guest user. Hope you're enjoying NeoGAF! Have you considered registering for an account? Come join us and add your take to the daily discourse.
Programming |OT| C is better than C++! No, C++ is better than C
- Thread starter Kikarian
- Start date
List is the primary collection type in C# and it's used for most things along with LINQ, there's usually not a good reason to use anything else. What are you trying to do?
Pokemaniac
Member
What I wanted was a list with the performance/memory profile of a linked list. I mean, technically I could probably just use an array-backed list (that is what List is, right? I forget if I managed to definitively determine that) and everything would probably be fine if I figured out an initial allocation to use, but why should I go through that trouble and waste the extra memory when a linked list provides exactly what I want. With C# being a pretty object oriented language, I figured this wouldn't be a huge deal, but no, LinkedList provides its own (worse) interface, which I can only assume exists due to some misguided attempt to protect the programmer from themselves.
Basically there's just a bunch of stuff which really feels like it should be largely interchangeable which just isn't, and I'm kind of baffled as to why.
Bony Manifesto
Member
Talking specifically about your problem, LinkedList doesn't implement IList because IList defines methods for adding and removing items at a specific index (as well as an indexer property), which obviously isn't appropriate for a linked list. I suspect that if you only wanted to add and remove items you should have used the simpler ICollection interface, which LinkedList does implement.
List is implemented with an array, yes. If you really must use LinkedList then use a linked list but as Bony points out the interface isn't what you think it is. The basic interface for collections is IEnumerable and it's best practice for functions to accept that as a parameter type versus something more concrete to use the biggest range of types. When you want to convert LINQ provides ToList() and ToArray() extension methods.
Pokemaniac
Member
Those operations that you're talking about are slower on a LinkedList, sure, but they don't make any less sense than having an array-backed list of dynamic size.
The two data types, while different in implementation, present essentially the same semantics. The differences between the two largely come down to implementation details, which really feels like something that should be abstracted from my code.
To be honest, I'm just really not sure what value is added by not making LinkedList implement IList.
The thing is, passing this list around isn't even the main issue I have. What I really take issue with is that if I want to have a LinkedList that is maintaining the internal state of an object, I need to directly interact with the nodes contained in it, which really just seems like a complete failure to provide any sort of useful abstraction between the various types of ordered collections. There's no middle ground between "this is a collection" and "this is a linked list"/"this is an array list".
Are you familiar with extension methods? This is exactly what LINQ does for things of type IEnumerable.
Pokemaniac
Member
I'm vaguely familiar with extension methods and LINQ, but short of implementing helper methods for things that really should be already in the language to begin with (at which point I might as well just use an alternate collections library) I'm not really sure how those are supposed to help me do simple things like getting the first element of a LinkedList in a way that isn't needlessly complicated.
Code:
var linkedList = new LinkedList<int>();
linkedList.AddLast(0);
linkedList.AddLast(1);
linkedList.AddLast(2);
linkedList.AddLast(3);
var first = linkedList.First(); //0
var firstOdd = linkedList.First(x => x % 2 == 1) //1
var last = linkedList.Last(); //3
var indexTwo = linkedList.ElementAt(2); //2
var hasFour = linkedList.Any(x => x == 4); //false
var oddCount = linkedList.Count(x => x % 2 == 1) //2
etc.Pokemaniac
Member
Huh, I didn't realize there was so much basic functionality hidden behind LINQ like that. I'll have to take a closer look at that.
Though, unless there's a linked list based stack hiding somewhere, I'm probably keeping this 3rd party collections library around. C# doesn't even seem to have a stack interface by default, only a single implementation (which is super weird. How does LinkedList of all things get an interface but not Stack).
cpp_is_king
Member
C#'s standard library data structures are garbage, not sure why they've never bothered to improve them. 3rd party collections library is basically necessary if you care even slightly about performance
Pokemaniac
Member
As C# collections libraries go, is C5 a good one to use or are there better ones I should look at?
Go on
cpp_is_king
Member
There are other data structures in the world besides lists, arrays, and dictionaries. And even among those 3, there are many different ways to implement them with different performance characteristics.. c# has perhaps the weakest collection library of any language I've used
They're pretty textbook implementations but that also means they are perfectly usable for the general case. If you have more knowledge about the domain then, sure, you can do better. I think most languages have decided standard libraries should offer good implementations of the most commonly used data structures, not every option and implementation but of course it's very opinionated.
God Enel
Member
Guys I'm no expert and I know that I can obviously use google but I like to have some quick info from some "pros" on what is useful and how hard it is to program an app for iphone and (later?) for android, (it is more or less nongraphical..)? What do I need? Some good resources on the language I will be programming with and information in general.
I have some basic logic of programming (c# and vba) can read code but it's not really great at all.
I have some basic logic of programming (c# and vba) can read code but it's not really great at all.
You could do both at once using Unity and C#.
Or you could learn Swift and Kotlin and do direct iOS/Android programming.
"good" is totallly relative.
Take a list, for example. If you want quick access to an indexed element, using a resizable array is the best approach. If you need to be able to add/remove at both ends, there's specific approaches that work better. If you want quick insertion, you'll prefer a linked list. If you want to be able to iterate both ways, a double-linked-list is better.
It's nice to have some choice in terms of underlying implementation. That often changes the complexity of functions you write, and has a direct impact on computation time.
That being said, I won't speak about C# in detail, I'm far from being a specialist. Initially, I would have agreed with Bony Manifesto, there's operations that are awful on linked lists, so avoiding providing those can be a safety measure (and LINQ is useful, in any case). But at the same time, it's also true that some unefficient operations are provided in other structures, so there's at least some inconsistency there...
It depends a LOT on what you want to create, and how. There's a huge variety of tools, including pure graphical tools that barely need any knowledge in programming (there's some really clever and interesting ones). At the same time, you may want to go down to the metal, including avoiding the "normal/official" development environments.
That's true but that's on the programmer to decide what they need for the task at hand. There's like a billion ways to have a balanced tree for instance, so maybe adding 50 implementations in the standard library isn't a good idea. In most cases there is a good-enough solution that works for the most common case. Obviously if you were doing low-memory programming an expanding array isn't a good choice for lists and stacks but most C# devs aren't doing that which is probably why there's not a focus on those implementations. To me it screams premature optimization, is your memory really exploding because the stack is implemented with an array? Even then if it's that critical you can spend the 15 mins to write your own implementation, the standard library in my mind is just saving me from writing it every single time when I don't care which is most of the time.
Pokemaniac
Member
I mean, I'm still going to be using a collections library that's written in C#. I'm just going to be using one that is much better designed from an OO standpoint and doesn't try to bind me to a specific implementation if I want anything more specific than a completely generic collection. The code I'm writing is going to be sensitive enough to performance that being able to tune my data structures properly could make a big difference.
Of course, if you were to write your own stack in C#, there'd be no good way for it to interoperate with other code that expects stacks, since the language doesn't even provide an interface you could implement for that one.
Which really just goes back to the point that there seems to have been very little thought put into the design of the default collections library from an OO standpoint.
I don't expect the standard library to be overly comprehensive, but there's like 2 major implementations of order preserving collections that you're going to be using the vast majority of the time, and they decided that one of them was important to include, but not important enough to actually make easily interchangeable with the other one, which is just bizarre in a language like C#.
I can agree with that. There are a few other areas that don't give you interfaces and it does get annoying when testing. Like I always need an ITimeProvider wrapper for DateTime because there is no interface so you can't stub DateTime.Now. Of course, I'm quicker to say this type of thing is just endemic of OO languages and their bad type systems. Why can't I just make my own interface and implement it on the object?
DateTime and TimeSpan leave much to be desired.
I do like ConcurrentCollections for Stacks/Queues.
Darryl M R
Member
I'm currently learning R through self teaching and my firm internal training team. I'm hoping to learn Phython soon after.
Any tips?
Any tips?
Not 50, definitively, but the most common solutions for lists seems a reasonable start.
I doubt it, but try an insertion-heavy algorithm with a list implemented as an array and you'll see your O(n³) killing you.
I'm perfectly fine with stack being an array, though. I doubt memory should be an issue in 99% cases... and in rare cases it doesn't work, it should be easy to implement a stack with a double-linked list. But a double-linked list seems a good candidate to be in the standard library.
By the way, I disagree that choosing the right representation for data is premature optimization (unless the structure has <10-20 elements, of course). In fact, I disagree with the idea it's optimization to begin with. "list" doesn't mean anything in algorithms.
(in fact, if a list is actually a resizable array under the hood, I think it should be called resizable array)
I think the standard library is there to avoid writing anything that is not an obscure structure. Because most of the time, by doing your own implemenentation, you'll do a poor job (because you won't be able to spend the time needed to do it properly) and make things worse for people that will have to work on your code.
(I'm playing the devil's advocate, I love writing my own implementations, but I'm working for myself, so there's no problem spending three weeks on designing a structure if I enjoy it, and I'll have less issues of interoperability)
List doesn't mean a whole lot, true. So I agree that better naming would make it more obvious what a typical operation should look like. Basic data structures like queues, stacks and vectors I don't sweat, any CS200 student has to build them, and in programming interviews those will come up so you have to be able to do them quickly and correctly. Only thing wouldn't touch is anything with hashing. I don't want to be on the hook for that.
Well... hashing itself is a really, really difficult task. Designing a k-universal hashing method (or a statistically close one, since in some cases it's impossible to strictly do this) is a job for mathematicians.
But at the same time, nobody expect you to design a new one, so all you need is to look for the right scientific paper and use their results.
Once you have your hashing function, most structures are straightforward. A dictionnary with hashing is basically either a simple table or a table of linked lists, for example.
AquaticSquirrel
Member
Hey guys quick question about testing with Python.
Is it better to have a separate test for every condition or is it better to group tests under a specific method?
What I mean by that is the following the best approach?:
Or should I make a separate test function for each test condition of a method?
LIke this?:
Or should I combine the two in someway like having one test method for each method contained in MyClass, and then have nested functions inside that method that tests each possible condition?
Is it better to have a separate test for every condition or is it better to group tests under a specific method?
What I mean by that is the following the best approach?:
Code:
import unittest
from my_module import MyClass
class TestMyClass(unittest.TestCase):
def setUp(self):
self.my_class = MyClass()
def test_first_method(self):
self.assertEqual('Condition 1', self.my_class.first_method(some_input))
self.assertEqual('Condition 2', self.my_class.first_method(some_input))
def test_second_method(self):
self.assertEqual('Condition 1', self.my_class.second_method(some_input))
self.assertEqual('Condition 2', self.my_class.second_method(some_input))
if __name__ == '__main__':
unittest.main()Or should I make a separate test function for each test condition of a method?
LIke this?:
Code:
import unittest
from my_module import MyClass
class TestMyClass(unittest.TestCase):
def setUp(self):
self.my_class = MyClass()
def test_first_method_condition_one(self):
self.assertEqual('Condition 1', self.my_class.first_method(some_input))
def test_first_method_condition_two(self):
self.assertEqual('Condition 2', self.my_class.first_method(some_input))
def test_second_method_condition_one(self):
self.assertEqual('Condition 1', self.my_class.second_method(some_input))
def test_second_method_condition_two(self):
self.assertEqual('Condition 2', self.my_class.second_method(some_input))
if __name__ == '__main__':
unittest.main()Or should I combine the two in someway like having one test method for each method contained in MyClass, and then have nested functions inside that method that tests each possible condition?
I'd say it's really up to you...
Do you want to ask "is my method correct? (if not, give me an example of what isn't working)" or "what are all the cases that my method fail to handle properly?"
In the first case, 1 method = 1 test method is the way to go. I'd say it's the most common situation, where you rely on unittest to validate a function and detect regressions.
But if you want to use unittest as an helper to development, I can see why it could be interesting to split them among different methods.
Maybe split them if you need help developing a method, then join them in a single method when it's working, so that you detect any bad change?
AquaticSquirrel
Member
I see so there is not exactly an accepted "right" approach for something like this then?
From what I understand based on your advice is that if I'm using TDD I should probably lean towards the 2nd style and then once I'm sure it covers all edge cases then I can refactor back to the first style?
But if I'm just using tests to make sure nothing breaks after I've already written the code then I should opt for style one.
What about nested functions grouped under each method that each contain one "assert" test case?
Randolph Freelander
Member
I'm in the camp that says each unit test should have only one (meaningful) assert. Tests should be specific. When a test fails, I shouldn't need to debug it to know which part failed (I might still need to debug to understand why), and an early assert failing shouldn't stop others from running (which means you should know all the problems from a single test run, not just the first problem with others potentially revealed later).
AquaticSquirrel
Member
I see so you are saying it's better to have separate methods to test specific behavior and edge cases with a single assert in each one.
I was leaning that way but I didn't want to do it the "wrong" way and pick up bad habits.
Thanks for the advice everyone!
If there's one, I've yet to hear about it. I'm pretty sure it's a matter of preferences.
I'm trying to see the pros and cons of both... I'd say it doesn't really matter at first (the goal is to pass all tests without failing!) So don't worry too much about this, do it as you're feeling it, and if it doesn't suit your needs, it's not a lot of work to switch the style...
It's pretty much the same as all tests in a single function. You'll still stop at the first assert failing, and you'll add some additional lines for nothing (and you're at risk of forgetting to call one function)
Well, you know which part failed... but indeed, you won't have all the details with a single test run. I think it's unfortunate...
But at the same time, if you have an heavy setup() and dozens of tests, it's not always practical to split everything. Also (although that's not a good con), I've usually seen people splitting everything writing a bit less test as a result (my statistical set is too small, mind you, but I'm not surprised).
I'd say it's a small flaw in unittest (you could solve it by subclassing it, but at the same time, having a standard tool is so nice you don't want to break this)
This could be a solution:
Code:
class RandomTest(unittest.TestCase):
def test(self) :
errors = []
try :
self.assertIn(1, ('a', 'b', 'c'))
except AssertionError as err :
errors += [repr(err)]
try :
self.assertIn(2, ('x', 'y', 'z'))
except AssertionError as err :
errors += [repr(err)]
self.assertEqual([], errors)CornBurrito
Member
My course is covering dynamic programming. I'm not sure if I really "get it".
I'm trying to find the minimum number of coins needed to make change for a given amount.
This does give me the correct answer. I've tried several different coin values and change amounts and it is correct. But looking around it seems like I'm supposed to be building up a 2D array? I'm not doing that. I'm just overwriting a 1D array as needed. Is this a violation of dynamic programming?
Also I can't for the life of me figure out how to modify my algorithm to also get which coins were used. I find the minimum, but idk how to get an array like: UsedCoins=[1,1,1,1] or UsedCoins=[0,0,0,1]. Where each value is how many of each denomination of the corresponding index.
I'm trying to find the minimum number of coins needed to make change for a given amount.
Code:
denoms = [1,2,4,8]
def getMinimum(denoms, change):
array = [0] * change
for i in range(0, amount):
for d in denoms:
if (d == (i+1)):
array[i] = 1
elif (d > i):
pass
else:
if (array[i] == 0):
array[i] = array[i - d] + 1
elif(array[i] > array[i - coin] + 1):
array[i] = array[ i- denom] + 1
return array[change-1]
print(getMinimum(denoms, 15))This does give me the correct answer. I've tried several different coin values and change amounts and it is correct. But looking around it seems like I'm supposed to be building up a 2D array? I'm not doing that. I'm just overwriting a 1D array as needed. Is this a violation of dynamic programming?
Also I can't for the life of me figure out how to modify my algorithm to also get which coins were used. I find the minimum, but idk how to get an array like: UsedCoins=[1,1,1,1] or UsedCoins=[0,0,0,1]. Where each value is how many of each denomination of the corresponding index.
cpp_is_king
Member
Think about it like this. Suppose you want to calculate the 10th Fibonacci number. You have to add the 9th and the 8th. But to calculate the 9th, you have to add the 8th and the 7th. So already you have to calculate the 8th twice. Why not, after calculating the first time, save the answer so that if you ever need it again you just return the previous answer.
This is where the array comes in. Every time you need to compute fib
you check the array, if the value is there just return it, otherwise calculate it, save the result in the array, then return it
This is where the array comes in. Every time you need to compute fib
you check the array, if the value is there just return it, otherwise calculate it, save the result in the array, then return itI can't really think of dynamic programming in the way it's typically described. Basically, I think of it as using recursion, the big problem is solved by applying the same logic to a subset, often choosing the "better" result. Then you basically cache the results for speed because it's often repetitive, ie memoization. Occasionally this will present a simplification where you can turn it into a nicer iterative representation.
For the coins, you return structures of coin type counts (probably array or struct) from the recursive function but internally to pick the best result you compare the coin count of the structure. You need a secondary structure like an array to store the previously calculated results (amount -> coin count values) to speed it up, but this doesn't impact the result.
For the coins, you return structures of coin type counts (probably array or struct) from the recursive function but internally to pick the best result you compare the coin count of the structure. You need a secondary structure like an array to store the previously calculated results (amount -> coin count values) to speed it up, but this doesn't impact the result.
CornBurrito
Member
Think about it like this. Suppose you want to calculate the 10th Fibonacci number. You have to add the 9th and the 8th. But to calculate the 9th, you have to add the 8th and the 7th. So already you have to calculate the 8th twice. Why not, after calculating the first time, save the answer so that if you ever need it again you just return the previous answer.
This is where the array comes in. Every time you need to compute fib
See, I thought that's what I'm doing. I do save the value. And I build up to "change" by starting from 1 and working my way up.
Sure, the saved values may get overwritten at some point but I don't think I ever need to recalculate something I overwrite during the course of the algorithms execution.
cpp_is_king
Member
For the coins problem, think of it like this.
What's the minimum number of coins with $4.62?
Well, one of the coins has to be either $.01, $.05, $.10, $.25, $.5, or $1
So that leaves you with a remainder of $4.61, $4.57, $4.52, $4.37, $4.12, or $3.62.
So the answer is 1 + min of those values
What's the minimum number of coins with $4.62?
Well, one of the coins has to be either $.01, $.05, $.10, $.25, $.5, or $1
So that leaves you with a remainder of $4.61, $4.57, $4.52, $4.37, $4.12, or $3.62.
So the answer is 1 + min of those values
cpp_is_king
Member
Oh you're wondering specifically about a 2d vs 1d array? No, I don't think this problem requires a 2d array, but there are definitely some that would
Royal_Phalanx
Member
As a still fairly new programmer how do you get past the impostor syndrome? Been having a lot of that feeling lately when I attend my local programming meetup. I feel incompetent when seeing other people's work.
Feeling this at work. Especially now that we pretty much have crunch time and I'm getting burned out quickly. Just going to try and push through it and try to learn as much as I can. Not even entirely sure that I'm cut out for dev work
Git gud. But seriously, you put a couple thousand hours into something, you become an expert. When you have imposter syndrome it means you're growing and you have identified things you don't know. If you don't have imposter syndrome, you have plateaued and don't know what you don't know. Just keep working at it. Also note that there's a million sub-niches, you won't be an expert at all of them, so sometimes you will be out of your league.
cpp_is_king
Member
You don't. If you don't have imposter syndrome, that's how you know it's time to seek a promotion or, failing that, move to a different company
Well, I have one hour to kill, and I'm feeling like discussing this dynamic programming a bit... Forgive me for the long post, I hope I'm not polluting the thread, and I post it in the remote chance it can be useful to someone...
I'm starting with basics, building up, catching some Python tricks along the way. The beginning is probably dead easy, I've written it partly as an attempt to lay some ideas for different kind of people, not as a direct reply, so you may jump a lot of things.
I agree with Somnid, dynamic programming is a child of recursion (the computation you're trying to do relies on similar, simpler computations) and memoization (remember the results you've already computed to avoid computing those several times).
Let's take for example fibonacci sequence, where
u_0 = 0
u_1 = 1
u_n = u_(n-1) + u(n-2) if n>1
The casual definition would be
Code:
def fibo(n) :
"""return the term u_n of Fibonacci sequence
where n is a positive integer"""
if n<2 :
return n
return fibo(n-1) + fibo(n-2)The problem with this definition is that you'll compute a lot of time the same thing. For example, for Fibo(5), you need Fibo(4) and Fibo(3), but Fibo(4) will also call Fibo(3), so it'll be computed twice. It grows exponentially from there.
So the solution can be memoization, remember already computed results :
Code:
# A list to remember first 100 u_n values, filling the first ones
_memory = [ 0, 1 ] + [ None ] * 98
def fibo(n) :
"""return the term u_n of Fibonacci sequence
where n is a positive integer"""
# if value has already been computed, return it
if _memory[n] is not None :
return _memory[n]
# if not, compute and memorize it, and return it
_memory[n] = fibo(n-1) + fibo(n-2)
return _memory[n]Now, _memory is a global variable, which is quite nasty. In C, you'd probably want something like a static variable, a variable in a function whose value is preserved between calls. No such thing in Python? Well, you could use algebraic closure, but there's a simpler solution: default parameters. Default parameters are "static" in Python, and evaluated at function definition (that's one of those sources of strange bugs). So you can write:
Code:
def fibo(n, *,
_memory = [ 0, 1 ] + [ None ] * 98) :
"""return the term u_n of Fibonacci sequence
where n is a positive integer"""
# if value has already been computed, return it
if _memory[n] is not None :
return _memory[n]
# if not, compute and memorize it, and return it
_memory[n] = fibo(n-1) + fibo(n-2)
return _memory[n]That's a bit better (* in arguments is a kind of trick, it makes _memory a keyword-only argument, just to be on the safer side... I also used the _ at the beginning of _memory only as a warning that the variable has some internal meaning, that may not be the best idea, but well...).
Now, the previous codes fail for n>=100. You can extend the list if needed:
Code:
def fibo(n, *,
_memory = [ 0, 1 ] + [ None ] * 98) :
"""return the term u_n of Fibonacci sequence
where n is a positive integer"""
# make sure the list can hold n+1 values
if len(_memory) < n+1 :
_memory.extend([None]*((n+1)-len(_memory))
# if value has already been computed, return it
if _memory[n] is not None :
return _memory[n]
# if not, compute and memorize it, and return it
_memory[n] = fibo(n-1) + fibo(n-2)
return _memory[n]Now, since you'll need to compute all u_p where 0<p<n to compute u_n, instead of a recursion, you can compute all of them, in a loop.
Code:
def fibo(n)
# Create a table just large enough,
# its content doesn't matter since you'll compute all u_p
# in order
memory = [ 0 ] * (n+1) :
# but we'll define initial values, u_0=0 and u_1=1
memory[1] = 1
# then we compute u_p where 2 <= p <= n
for p in range(2, n+1) :
memory[p] = memory[p-1] + memory[p-2]
# and return the expected result
return memory[n]This last solution is a typical example of dynamic programming: solve problems of increasing difficulty (fibo(p) with increasing p) while memorizing the results and using the results of previous steps, till you solve the problem you wanted to solve.
Some remarks:
- this solution is better in Python (actually in most languages, but especially in Python) than recursive ones, because recursivity is inefficient (by design)... you especially won't be able to recursively compute u_1000 because there's a limit on recursive calls (well, you technically could change some Python parameters, but you probably shouldn't).
- if you call the function several times, you'll compute several times the same values, so making the memory list "static" would still be nice, but I'll avoid doing it here to keep things simple
- you'll quickly see you only need the last two values to compute any subsequent value, so this function would be more efficiently written
Code:
def fibo(n) :
if n<2 :
return n
u, v = 0, 1
for p in range(2, n+1) :
u, v = v, u+v
return vNow, on your "money" problem... I'll change a little bit a couple of things of your program to make things simpler.
memory will be a list so that memory[p] contains minimum number of coins you need to get the amount p.
memory[0] is obviously 0
In a dynamic programming scheme, we'll now compute memory[p] for p=1, then p=2, 3... n
For each coin c <= p, you can get the amount p by adding the coin c to the amount p-c. If you need k coins to get the amount p-c, you can get the amount p with k+1 coins at most.
If k+1 must be the smallest possible value, you want k to be as small as possible, and look for the coin c that gives you the smallest k.
So, obviously, as Cpp_is_kind stated, you have
memory[p] = 1 + min( memory[p-c] for all coins c<=p )
The code could simply be
Code:
def GetMinimum(denoms, change) :
# All results are unknown at first, except memory[0] = 0
# The other values don't matter, since they'll be updated
memory = [ 0 ] * (change+1)
# Let's compute all memory[p] using the formula
for p in range(min(denoms), change+1) :
memory[p] = 1 + min(memory[p-c] for c in denoms if p>=c)
return memory[change]It's the exact same idea as your code, but I think it's easier to read/understand (?)
Well... if I want to go into details, that will work 99% of the time. It'll work all the time with *real* sets of coins (obviously... you don't want a coin set that is unable to produce some amounts!).
But if you want to be cautious, there's a chance that the min() function try to work with an empty list (for example, when you try to compute memory[1] of all coins are >1...) Let's go further, and use None as a result for amounts you can't obtain with the set of coins.
Code:
def GetMini(denoms, change) :
# All results are unknown at first, except _memory[0] = 0
# The other values don't really matter, but let's assume it's impossible by
# default, so that we don't have to change the value if no solution is found
memory = [ None ] * (change+1)
memory[0] = 0
# Let's compute all _memory[p] with increasing p
for p in range(min(denoms), change+1) :
candidates = [ memory[p-c] for c in denoms if p>=c and memory[p-c] is not None ]
# If at least a solution exists, compute memory[p]
if len(candidates) > 0 :
memory[p] = 1 + min(candidates)
return memory[change]It could also be done with exceptions, putting the min(...) in the previous code in a try ... except. Same result.
Let's assume now that you want the solution, not the number of coins. You can use memory[p] list to store the best solutions for an amount p, instead of the number of coins. Those solutions can be list of coins.
We still compute all memory[p] for increasing p, and for each p, we retrieve all solutions for p-c (assuming p-c can be done), keep the shortest one, and add the corresponding coin to the list.
It's barely harder (but getting the shortest list and the corresponding coin among all possibilites is a bit longer)
Code:
def GetMini(denoms, change) :
# All results are unknown at first, except _memory[0] = 0
# The other values don't really matter, but let's assume it's impossible by
# default, so that we don't have to change the value if no solution is found
memory = [ None ] * (change+1)
memory[0] = []
# Let's compute all memory[p] with increasing p
for p in range(min(denoms), change+1) :
# Look, for each coin c, the best solution for amount p-c (if possible)
candidates = [ (c, memory[p-c]) for c in denoms if p>=c and memory[p-c] is not None ]
# if there's at least a solution
if len(candidates) > 0 :
# Look for the shortest one
newcoin, bestsol = candidates[0]
for coin, sol in candidates :
if len(sol) < len(bestsol) :
newcoin, bestsol = coin, sol
# Keep, for the amount p, the shortest solution for p-c, and add the coin c
memory[p] = bestsol.copy()
memory[p].append(newcoin)
return memory[change]Note that this algorithm gives you a set of coins, not the number of each coin needed. But it should be trivial to change (start with [0]*len(denoms), and +1 one of the values of the copied lists instead of appending newcoin...)
As a closing remark, this algorithm works with any set of coins, but for "normal" set of coins (=canonical sets*), a greedy algorithm will provide the best solution faster.
* most countries in the world use canonical sets of coins. One example of non-canonical set, where finding the best solution is harder, is for example the former british system...
Sorry again for this long post...
Wondering if anyone can help me understand a quick scoping question in Angular 2? I'm picking up code from a previous co-op student and learning it as I go, so I'm pretty new to it.
So within one of the component.ts files, there's a class:
This will work just fine, but if in different component.ts file, I need to call a function within the PendingListComponent class, as far as I can tell I need to make that a public static function?
However, when I do this and do an 'npm start', I get an error saying
If I go ahead and modify the code so that it looks like this:
Then npm no longer complains.
My question is, is there anyway I can get the variable PendingListComponent.db_name and pass it into the
public static getDbName()
function?
So within one of the component.ts files, there's a class:
Code:
export class PendingListComponent implements OnInit, OnDestroy {
...
db_name: string = "myDBname"
...
getLibraryFromDatabase() {
this.subscription = this.libraryService.getLibraryFromDatabase(this.db_name)
.subscribe(libs => {this.libraries = libs; this.errorMsg = null;},
error => this.errorMsg = error);
}
}This will work just fine, but if in different component.ts file, I need to call a function within the PendingListComponent class, as far as I can tell I need to make that a public static function?
Code:
export class PendingListComponent implements OnInit, OnDestroy {
...
public static get getDbName(): string{
return this.db_name;
}
}However, when I do this and do an 'npm start', I get an error saying
Code:
app/component/pendingPage/pendingList.component.ts(81,16): error TS2339: Property 'db_name' does not exist on type 'typeof PendingListComponent'.If I go ahead and modify the code so that it looks like this:
Code:
export class PendingListComponent implements OnInit, OnDestroy {
...
db_name: string = "myDBname"
public static db_name: string = "myDBname"; // Note how I've added another declaration of db_name as a public static variable
...
getLibraryFromDatabase() {
this.subscription = this.libraryService.getLibraryFromDatabase(this.db_name)
.subscribe(libs => {this.libraries = libs; this.errorMsg = null;},
error => this.errorMsg = error);
}
...
public static get getDbName(): string{
return this.db_name;
}
}Then npm no longer complains.
My question is, is there anyway I can get the variable PendingListComponent.db_name and pass it into the
public static getDbName()
function?
I wouldn't use static variables, except in some real weird cases. The simple solution is just above the class declaration in your module: const db_name = "my_dbname"; Now it's constant but scoped to the module not an instance. If something else needs it, then export it. If you have some other thing like a config or whatever that fills that in then you'd build the provider and dependency inject it.
Lister
Banned
Not directly answering the question as that was done above, but since you're starting out with Angular 2 I figure I'd dispense some basic advice. It looks like you have a smart component and a dumb component and are trying to access a property of the smart compoenent from the dumb one (the database uri).
Accessing this property directly is not how you shoudl be doing this. You have a coupel of options:
1. The dumb component uses the Input() decorator on one of it's properties and the smart component passes down the info in the view template:
In the dumb.compoenent.ts:
Code:
export class DumbComponent {
@Input() dbUrl: string;
}In the view of smart.compoenent.ts:
Code:
<app-dumb-component [dbUrl]="dbUrl"></app-dumb-component>2. You could use a service to communicate this information. This is probably the way to go when it comes to somehting like accessing http to communicate with a server.
Simply create a service that exposes an API for server communication, provide it on your root (app) element (if it's intended as a singleton), and have it injected into any component that needs to talk to the server.
server-db.service.ts
Code:
import { Widget } from '';
@inject()
export class ServerDbService {
private readonly const dbEndPoint: string = 'blahblah.com';
contructor(private http: Http){}
// You could also return a promise isntead of na observable.
loadDocument(): Observable<Widget> {
return http.get(this.dbEndpoint)
.map(resp => resp.json());
}
etc....
}app.module.ts
Code:
@NgModule({
imports: [ ],
declarations: [
AppComponent
],
providers: [ServerDbService],
bootstrap: [AppComponent]
})
export class AppModule { }x.component.ts
Code:
export class DumbComponent {
constructor(private dbService: ServerDbService){}
clickedLoadButton(): void {
this.dbService.loadDocument()
.subcribe((widget: Widget) => { do something; });
}
}'course the cool thing about observables is that you don't need to subscribe to them in your component, but can use them directly on your view by leveraging the async pipe (observable$ | async).
C# and VB.Net are splitting finally it looks like...
I'm kinda sad because the workplace is a VB.Net shop (tons of old VBA/Access stuff still being used/modified to this day) so everything I write has to be VB.Net. It's not the worst, but being able to do stuff in C# and bring it to VB.Net with minor tweaks was always nice.
I'm kinda sad because the workplace is a VB.Net shop (tons of old VBA/Access stuff still being used/modified to this day) so everything I write has to be VB.Net. It's not the worst, but being able to do stuff in C# and bring it to VB.Net with minor tweaks was always nice.
Lister
Banned
Linky?