Optimization using Hill Climbing

The following example shows how to find the best portfolio configuration given that only the price of a single stock can be incremented by 10 cents at a time. Since we are using Hill Climbing technique, we can find the local optimal value easily but the same cannot be said for finding the global optimal value, unless you continuously repeat the climbing procedure in an iterative manner or use variable number of restarts.

portfolio = {
                'VRNG'  : 3.54,
                'BBY'   : 13.75,
                'AMD'   : 1.86,
                'S'     : 5.48,
                'CHK'   : 16.62,
                'CLWR'  : 2.19,
                'SCGLY' : 6.22,
                'HES'   : 48.91,
                'BAC'   : 9.12,
                'FB'    : 23.56
            }

stockCount = [random.randint(10, 100) // 10 * 10 for k in portfolio]

def optimize():
    """ Using Hill Climbing technique to find total valuation of a portfolio due
     to 10BP (Basis Point) movement in the price of the stock.
     Assuming I own 100 quantities of each stock """

    import sys
    bestValue = -sys.maxint
    bestPrices = None
    stockNames = portfolio.keys()
    stockPrices = [portfolio[k] for k in stockNames]

##    print 'Your current portfolio contains the following stocks:'
    from itertools import izip
##    for sn, sp, sc in izip(stockNames, stockPrices, stockCount):
##        print '{0:5} {1:5} {2:5}'.format(sn, sc, sp)
##    print

    neighbours = []
    for idx in xrange(len(stockPrices)):
        neighbours.append(stockPrices[ :idx] + [stockPrices[idx] - 0.10] + stockPrices[idx + 1 :])
        neighbours.append(stockPrices[ :idx] + [stockPrices[idx] + 0.10] + stockPrices[idx + 1 :])

    def computeSum(arr):
        return sum([sp * sc for sp, sc in izip(arr, stockCount)])

    currValuation = computeSum(stockPrices)
    for n in neighbours:
        newValuation = computeSum(n)
        if newValuation > bestValue:
            bestValue = newValuation
            bestPrices = n

    if currValuation == bestValue:
        print 'Current Portfolio value will still remain profitable!'
    else:
        print 'Possibility to make a profit of $%s with the following portfolio (using Hill Climbing): ' % (bestValue - currValuation)
        print 'Name     Qty     Old        New     chg'
        for sn, sp, bp, sc in izip(stockNames, stockPrices, bestPrices, stockCount):
            print '{0:5} {4:5} {1:10} {2:10} {3:5}'.format(sn, sp, bp, bp - sp, sc)
        print 'Original Valuation: %s Profitable Valuation: %s' % (currValuation, bestValue)


def main():
    optimize()

Output:

>>> 
Quite possible to make a profit of $9.0 with the following portfolio (using Hill Climbing): 
Name     Qty     Old        New     chg
HES      30      48.91      48.91   0.0
S        80       5.48       5.48   0.0
BAC      30       9.12       9.12   0.0
BBY      90      13.75      13.85   0.1
SCGLY    90       6.22       6.22   0.0
VRNG     50       3.54       3.54   0.0
FB       70      23.56      23.56   0.0
CHK      50      16.62      16.62   0.0
AMD      70       1.86       1.86   0.0
CLWR     20       2.19       2.19   0.0
Original Valuation: 6807.8 Profitable Valuation: 6816.8
>>> 
Quite possible to make a profit of $10.0 with the following portfolio (using Hill Climbing): 
Name     Qty     Old        New     chg
HES      60      48.91      48.91   0.0
S        70       5.48       5.48   0.0
BAC      90       9.12       9.12   0.0
BBY      50      13.75      13.75   0.0
SCGLY    30       6.22       6.22   0.0
VRNG     60       3.54       3.54   0.0
FB      100      23.56      23.66   0.1
CHK      10      16.62      16.62   0.0
AMD      90       1.86       1.86   0.0
CLWR     90       2.19       2.19   0.0
Original Valuation: 8112.2 Profitable Valuation: 8122.2

Posted on November 15, 2012 by GauZ in Python

Tags: , , , , , ,

0  

Prefix Tree

Creating a prefix tree is quite easy in Python!

root = {}

def addToTree(node, word=()):
        if not word: return

        addToTree(node.setdefault(word[0], {}), word[1: ])

def main():
        for word in ('batman', 'bane', 'bale',):
                addToTree(root, word)
        print root

Output:

{'b': {
        'a': {
            'l': {
                'e': {}
                 }, 
            'n': {
                'e': {}
                 }, 
            't': {
                'm': {
                    'a': {
                        'n': {}
                         }
                     }
                 }
             }
       }
}

Posted on November 10, 2012 by GauZ in Python, Technology

Tags: , , , , ,

0  

Do Value Types in C# always go on the stack?

It is quite well-known that value-types are created on the Stack (sometimes in registers as well depending on the allocation strategy) and reference types are based in the Heap area of memory. But when you are creating a custom type and you wish to embed value types in there, where would they reside?

So it depends on the context. If a value type is being created as a local or rather temporary variable in a function, then they will always lie in the stack or registers otherwise they will reside where they are created – which in this case happens to be the heap.

For more information, please refer – http://blogs.msdn.com/b/ericlippert/archive/2010/09/30/the-truth-about-value-types.aspx

Posted on November 3, 2012 by GauZ in C#

Tags: , , , , ,

0  

Another way to print hex value in C++

You can simply use the std::hex base format flag! This also works with oct and dec.

#include <iostream>

int main() {
    std::cout << "Value of 10 in hex: " << std::hex << 10 << std::endl;
    std::cout << "Value of 10 in dec: " << std::dec << 10 << std::endl;
    std::cout << "Value of 10 in oct: " << std::oct << 10 << std::endl;

    getchar();
}

Output:

Value of 10 in hex: a

Value of 10 in dec: 10

Value of 10 in oct: 12

Posted on November 1, 2012 by GauZ in C++

Tags: , , , , , , , , ,

0  

Pass a STL Array of fixed size as a parameter to another function without declaring the size in the function signature or prototype

There are two ways of doing this. You can either pass in a pointer/reference to the array along with it’s size to the function.

#include <iostream>
#include <array>

void swap(int *arr, int a, int b) {
    auto t  = arr[a];
    arr[a] = arr[b];
    arr[b] = t;
}

int partition(int *arr, int low, int high) {
    swap(arr, high, (low + high) / 2);

    auto store = low;
    for (auto i = low; i < high; i++) {
        if (arr[i] <= arr[high])
            swap(arr, store++, i);
    }

    swap(arr, store, high);
    return store;
}

void quickSort(int *arr, int low, int high) {
    if (low <= high) {
        auto p = partition(arr, low, high);
        quickSort(arr, low, p - 1);
        quickSort(arr, p + 1, high);
    }
}

void display(int *arr, int size) {
    for (auto i = 0; i < size; i++)
        std::cout << *(arr + i) << " ";
    std::cout << std::endl;
}

int main() {
    std::array<int, 9> arr = {9, 6, 3, 8, 1, 5, 2, 4, 7};
    std::cout << "Before sorting ..." << std::endl;
    display(arr.data(), arr.size());

    quickSort(arr.data(), 0, arr.size() - 1);

    std::cout << "After sorting ..." << std::endl;
    display(arr.data(), arr.size());

    getchar();
}

But, this is not really convenient. Another way would be to hardcode the size of the array in the function prototype which is BAD code and we should try to create a generic function capable of handling array of any size.

So, we will use function templates. SmileNow, there is no need to pass in the size of the array at all!

#include <iostream>
#include <array>

template<size_t N>
void swap(std::array<int, N>& arr, int a, int b) {
    auto t  = arr[a];
    arr[a] = arr[b];
    arr[b] = t;
}

template<size_t N>
void quickSort(std::array<int, N>& arr, int low, int high) {
    if (low <= high) {
        auto p = partition(arr, low, high);
        quickSort(arr, low, p - 1);
        quickSort(arr, p + 1, high);
    }
}

template<size_t N>
int partition(std::array<int, N>& arr, int low, int high) {
    swap(arr, high, (low + high) / 2);

    auto store = low;
    for (auto i = low; i < high; i++) {
        if (arr[i] <= arr[high])
            swap(arr, store++, i);
    }

    swap(arr, store, high);
    return store;
}

template<size_t N>
void display(std::array<int, N> const& arr) {
    for (auto i = arr.begin(); i != arr.end(); i++)
        std::cout << *i << " ";
    std::cout << std::endl;
}

int main() {
    std::array<int, 9> arr = {9, 6, 3, 8, 1, 5, 2, 4, 7};
    std::cout << "Before sorting ..." << std::endl;
    display(arr);

    quickSort(arr, 0, arr.size() - 1);

    std::cout << "After sorting ..." << std::endl;
    display(arr);

    getchar();
}

Posted on October 12, 2012 by GauZ in C++

Tags: , , , , , , , ,

0