Search Results

Search found 5070 results on 203 pages for 'algorithm'.

Page 196/203 | < Previous Page | 192 193 194 195 196 197 198 199 200 201 202 203  | Next Page >

• mdadm raid5 recover double disk failure - with a twist (drive order)

  - by Peter Bos

  Let me acknowledge first off that I have made mistakes, and that I have a backup for most but not all of the data on this RAID. I still have hope of recovering the rest of the data. I don't have the kind of money to take the drives to a recovery expert company. Mistake #0, not having a 100% backup. I know. I have a mdadm RAID5 system of 4x3TB. Drives /dev/sd[b-e], all with one partition /dev/sd[b-e]1. I'm aware that RAID5 on very large drives is risky, yet I did it anyway. Recent events The RAID become degraded after a two drive failure. One drive [/dev/sdc] is really gone, the other [/dev/sde] came back up after a power cycle, but was not automatically re-added to the RAID. So I was left with a 4 device RAID with only 2 active drives [/dev/sdb and /dev/sdd]. Mistake #1, not using dd copies of the drives for restoring the RAID. I did not have the drives or the time. Mistake #2, not making a backup of the superblock and mdadm -E of the remaining drives. Recovery attempt I reassembled the RAID in degraded mode with mdadm --assemble --force /dev/md0, using /dev/sd[bde]1. I could then access my data. I replaced /dev/sdc with a spare; empty; identical drive. I removed the old /dev/sdc1 from the RAID mdadm --fail /dev/md0 /dev/sdc1 Mistake #3, not doing this before replacing the drive I then partitioned the new /dev/sdc and added it to the RAID. mdadm --add /dev/md0 /dev/sdc1 It then began to restore the RAID. ETA 300 mins. I followed the process via /proc/mdstat to 2% and then went to do other stuff. Checking the result Several hours (but less then 300 mins) later, I checked the process. It had stopped due to a read error on /dev/sde1. Here is where the trouble really starts I then removed /dev/sde1 from the RAID and re-added it. I can't remember why I did this; it was late. mdadm --manage /dev/md0 --remove /dev/sde1 mdadm --manage /dev/md0 --add /dev/sde1 However, /dev/sde1 was now marked as spare. So I decided to recreate the whole array using --assume-clean using what I thought was the right order, and with /dev/sdc1 missing. mdadm --create /dev/md0 --assume-clean -l5 -n4 /dev/sdb1 missing /dev/sdd1 /dev/sde1 That worked, but the filesystem was not recognized while trying to mount. (It should have been EXT4). Device order I then checked a recent backup I had of /proc/mdstat, and I found the drive order. md0 : active raid5 sdb1[0] sde1[4] sdd1[2] sdc1[1] 8790402048 blocks super 1.2 level 5, 512k chunk, algorithm 2 [4/4] [UUUU] I then remembered this RAID had suffered a drive loss about a year ago, and recovered from it by replacing the faulty drive with a spare one. That may have scrambled the device order a bit...so there was no drive [3] but only [0],[1],[2], and [4]. I tried to find the drive order with the Permute_array script: https://raid.wiki.kernel.org/index.php/Permute_array.pl but that did not find the right order. Questions I now have two main questions: I screwed up all the superblocks on the drives, but only gave: mdadm --create --assume-clean commands (so I should not have overwritten the data itself on /dev/sd[bde]1. Am I right that in theory the RAID can be restored [assuming for a moment that /dev/sde1 is ok] if I just find the right device order? Is it important that /dev/sde1 be given the device number [4] in the RAID? When I create it with mdadm --create /dev/md0 --assume-clean -l5 -n4 \ /dev/sdb1 missing /dev/sdd1 /dev/sde1 it is assigned the number [3]. I wonder if that is relevant to the calculation of the parity blocks. If it turns out to be important, how can I recreate the array with /dev/sdb1[0] missing[1] /dev/sdd1[2] /dev/sde1[4]? If I could get that to work I could start it in degraded mode and add the new drive /dev/sdc1 and let it resync again. It's OK if you would like to point out to me that this may not have been the best course of action, but you'll find that I realized this. It would be great if anyone has any suggestions.

  Read the article

• being able to solve google code jam problem sets

  - by JPro

  This is not a homework question, but rather my intention to know if this is what it takes to learn programming. I keep loggin into TopCoder not to actually participate but to get the basic understand of how the problems are solved. But to my knowledge I don't understand what the problem is and how to translate the problem into an algorithm that can solve it. Just now I happen to look at ACM ICPC 2010 World Finals which is being held in china. The teams were given problem sets and one of them is this: Given at most 100 points on a plan with distinct x-coordinates, find the shortest cycle that passes through each point exactly once, goes from the leftmost point always to the right until it reaches the rightmost point, then goes always to the left until it gets back to the leftmost point. Additionally, two points are given such that the the path from left to right contains the first point, and the path from right to left contains the second point. This seems to be a very simple DP: after processing the last k points, and with the first path ending in point a and the second path ending in point b, what is the smallest total length to achieve that? This is O(n^2) states, transitions in O(n). We deal with the two special points by forcing the first path to contain the first one, and the second path contain the second one. Now I have no idea what I am supposed to solve after reading the problem set. and there's an other one from google code jam: Problem In a big, square room there are two point light sources: one is red and the other is green. There are also n circular pillars. Light travels in straight lines and is absorbed by walls and pillars. The pillars therefore cast shadows: they do not let light through. There are places in the room where no light reaches (black), where only one of the two light sources reaches (red or green), and places where both lights reach (yellow). Compute the total area of each of the four colors in the room. Do not include the area of the pillars. Input * One line containing the number of test cases, T. Each test case contains, in order: * One line containing the coordinates x, y of the red light source. * One line containing the coordinates x, y of the green light source. * One line containing the number of pillars n. * n lines describing the pillars. Each contains 3 numbers x, y, r. The pillar is a disk with the center (x, y) and radius r. The room is the square described by 0 = x, y = 100. Pillars, room walls and light sources are all disjoint, they do not overlap or touch. Output For each test case, output: Case #X: black area red area green area yellow area Is it required that people who program should be should be able to solve these type of problems? I would apprecite if anyone can help me interpret the google code jam problem set as I wish to participate in this years Code Jam to see if I can do anthing or not. Thanks.

  Read the article

• fd partitions gone from 2 discs, md happy with it and resyncs. How to recover ?

  - by d0nd

  Hey gurus, need some help badly with this one. I run a server with a 6Tb md raid5 volume built over 7*1Tb disks. I've had to shut down the server lately and when it went back up, 2 out of the 7 disks used for the raid volume had lost its conf : dmesg : [ 10.184167] sda: sda1 sda2 sda3 // System disk [ 10.202072] sdb: sdb1 [ 10.210073] sdc: sdc1 [ 10.222073] sdd: sdd1 [ 10.229330] sde: sde1 [ 10.239449] sdf: sdf1 [ 11.099896] sdg: unknown partition table [ 11.255641] sdh: unknown partition table All 7 disks have same geometry and were configured alike : dmesg : Disk /dev/sdb: 1000.2 GB, 1000204886016 bytes 255 heads, 63 sectors/track, 121601 cylinders Units = cylinders of 16065 * 512 = 8225280 bytes Disk identifier: 0x1e7481a5 Device Boot Start End Blocks Id System /dev/sdb1 1 121601 976760001 fd Linux raid autodetect All 7 disks (sdb1, sdc1, sdd1, sde1, sdf1, sdg1, sdh1) were used in a md raid5 xfs volume. When booting, md, which was (obviously) out of sync kicked in and automatically started rebuilding over the 7 disks, including the two "faulty" ones; xfs tried to do some shenanigans as well: dmesg : [ 19.566941] md: md0 stopped. [ 19.817038] md: bind<sdc1> [ 19.817339] md: bind<sdd1> [ 19.817465] md: bind<sde1> [ 19.817739] md: bind<sdf1> [ 19.817917] md: bind<sdh> [ 19.818079] md: bind<sdg> [ 19.818198] md: bind<sdb1> [ 19.818248] md: md0: raid array is not clean -- starting background reconstruction [ 19.825259] raid5: device sdb1 operational as raid disk 0 [ 19.825261] raid5: device sdg operational as raid disk 6 [ 19.825262] raid5: device sdh operational as raid disk 5 [ 19.825264] raid5: device sdf1 operational as raid disk 4 [ 19.825265] raid5: device sde1 operational as raid disk 3 [ 19.825267] raid5: device sdd1 operational as raid disk 2 [ 19.825268] raid5: device sdc1 operational as raid disk 1 [ 19.825665] raid5: allocated 7334kB for md0 [ 19.825667] raid5: raid level 5 set md0 active with 7 out of 7 devices, algorithm 2 [ 19.825669] RAID5 conf printout: [ 19.825670] --- rd:7 wd:7 [ 19.825671] disk 0, o:1, dev:sdb1 [ 19.825672] disk 1, o:1, dev:sdc1 [ 19.825673] disk 2, o:1, dev:sdd1 [ 19.825675] disk 3, o:1, dev:sde1 [ 19.825676] disk 4, o:1, dev:sdf1 [ 19.825677] disk 5, o:1, dev:sdh [ 19.825679] disk 6, o:1, dev:sdg [ 19.899787] PM: Starting manual resume from disk [ 28.663228] Filesystem "md0": Disabling barriers, not supported by the underlying device [ 28.663228] XFS mounting filesystem md0 [ 28.884433] md: resync of RAID array md0 [ 28.884433] md: minimum _guaranteed_ speed: 1000 KB/sec/disk. [ 28.884433] md: using maximum available idle IO bandwidth (but not more than 200000 KB/sec) for resync. [ 28.884433] md: using 128k window, over a total of 976759936 blocks. [ 29.025980] Starting XFS recovery on filesystem: md0 (logdev: internal) [ 32.680486] XFS: xlog_recover_process_data: bad clientid [ 32.680495] XFS: log mount/recovery failed: error 5 [ 32.682773] XFS: log mount failed I ran fdisk and flagged sdg1 and sdh1 as fd. I tried to reassemble the array but it didnt work: no matter what was in mdadm.conf, it still uses sdg and sdh instead of sdg1 and sdh1. I checked in /dev and I see no sdg1 and and sdh1, shich explains why it wont use it. I just don't know why those partitions are gone from /dev and how to readd those... blkid : /dev/sda1: LABEL="boot" UUID="519790ae-32fe-4c15-a7f6-f1bea8139409" TYPE="ext2" /dev/sda2: TYPE="swap" /dev/sda3: LABEL="root" UUID="91390d23-ed31-4af0-917e-e599457f6155" TYPE="ext3" /dev/sdb1: UUID="2802e68a-dd11-c519-e8af-0d8f4ed72889" TYPE="mdraid" /dev/sdc1: UUID="2802e68a-dd11-c519-e8af-0d8f4ed72889" TYPE="mdraid" /dev/sdd1: UUID="2802e68a-dd11-c519-e8af-0d8f4ed72889" TYPE="mdraid" /dev/sde1: UUID="2802e68a-dd11-c519-e8af-0d8f4ed72889" TYPE="mdraid" /dev/sdf1: UUID="2802e68a-dd11-c519-e8af-0d8f4ed72889" TYPE="mdraid" /dev/sdg: UUID="2802e68a-dd11-c519-e8af-0d8f4ed72889" TYPE="mdraid" /dev/sdh: UUID="2802e68a-dd11-c519-e8af-0d8f4ed72889" TYPE="mdraid" fdisk -l : Disk /dev/sda: 40.0 GB, 40020664320 bytes 255 heads, 63 sectors/track, 4865 cylinders Units = cylinders of 16065 * 512 = 8225280 bytes Disk identifier: 0x8c878c87 Device Boot Start End Blocks Id System /dev/sda1 * 1 12 96358+ 83 Linux /dev/sda2 13 134 979965 82 Linux swap / Solaris /dev/sda3 135 4865 38001757+ 83 Linux Disk /dev/sdb: 1000.2 GB, 1000204886016 bytes 255 heads, 63 sectors/track, 121601 cylinders Units = cylinders of 16065 * 512 = 8225280 bytes Disk identifier: 0x1e7481a5 Device Boot Start End Blocks Id System /dev/sdb1 1 121601 976760001 fd Linux raid autodetect Disk /dev/sdc: 1000.2 GB, 1000204886016 bytes 255 heads, 63 sectors/track, 121601 cylinders Units = cylinders of 16065 * 512 = 8225280 bytes Disk identifier: 0xc9bdc1e9 Device Boot Start End Blocks Id System /dev/sdc1 1 121601 976760001 fd Linux raid autodetect Disk /dev/sdd: 1000.2 GB, 1000204886016 bytes 255 heads, 63 sectors/track, 121601 cylinders Units = cylinders of 16065 * 512 = 8225280 bytes Disk identifier: 0xcc356c30 Device Boot Start End Blocks Id System /dev/sdd1 1 121601 976760001 fd Linux raid autodetect Disk /dev/sde: 1000.2 GB, 1000204886016 bytes 255 heads, 63 sectors/track, 121601 cylinders Units = cylinders of 16065 * 512 = 8225280 bytes Disk identifier: 0xe87f7a3d Device Boot Start End Blocks Id System /dev/sde1 1 121601 976760001 fd Linux raid autodetect Disk /dev/sdf: 1000.2 GB, 1000204886016 bytes 255 heads, 63 sectors/track, 121601 cylinders Units = cylinders of 16065 * 512 = 8225280 bytes Disk identifier: 0xb17a2d22 Device Boot Start End Blocks Id System /dev/sdf1 1 121601 976760001 fd Linux raid autodetect Disk /dev/sdg: 1000.2 GB, 1000204886016 bytes 255 heads, 63 sectors/track, 121601 cylinders Units = cylinders of 16065 * 512 = 8225280 bytes Disk identifier: 0x8f3bce61 Device Boot Start End Blocks Id System /dev/sdg1 1 121601 976760001 fd Linux raid autodetect Disk /dev/sdh: 1000.2 GB, 1000204886016 bytes 255 heads, 63 sectors/track, 121601 cylinders Units = cylinders of 16065 * 512 = 8225280 bytes Disk identifier: 0xa98062ce Device Boot Start End Blocks Id System /dev/sdh1 1 121601 976760001 fd Linux raid autodetect I really dont know what happened nor how to recover from this mess. Needless to say the 5TB or so worth of data sitting on those disks are very valuable to me... Any idea any one? Did anybody ever experienced a similar situation or know how to recover from it ? Can someone help me? I'm really desperate... :x

  Read the article

• Problem with memset after an instance of a user defined class is created and a file is opened

  - by Liberalkid

  I'm having a weird problem with memset, that was something to do with a class I'm creating before it and a file I'm opening in the constructor. The class I'm working with normally reads in an array and transforms it into another array, but that's not important. The class I'm working with is: #include <vector> #include <algorithm> using namespace std; class PreProcess { public: PreProcess(char* fileName,char* outFileName); void SortedOrder(); private: vector< vector<double > > matrix; void SortRow(vector<double> &row); char* newFileName; vector< pair<double,int> > rowSorted; }; The other functions aren't important, because I've stopped calling them and the problem persists. Essentially I've narrowed it down to my constructor: PreProcess::PreProcess(char* fileName,char* outFileName):newFileName(outFileName){ ifstream input(fileName); input.close(); //this statement is inconsequential } I also read in the file in my constructor, but I've found that the problem persists if I don't read in the matrix and just open the file. Essentially I've narrowed it down to if I comment out those two lines the memset works properly, otherwise it doesn't. Now to the context of the problem I'm having with it: I wrote my own simple wrapper class for matrices. It doesn't have much functionality, I just need 2D arrays in the next part of my project and having a class handle everything makes more sense to me. The header file: #include <iostream> using namespace std; class Matrix{ public: Matrix(int r,int c); int &operator()(int i,int j) {//I know I should check my bounds here return matrix[i*columns+j]; } ~Matrix(); const void Display(); private: int *matrix; const int rows; const int columns; }; Driver: #include "Matrix.h" #include <string> using namespace std; Matrix::Matrix(int r,int c):rows(r),columns(c) { matrix=new int[rows*columns]; memset(matrix,0,sizeof(matrix)); } const void Matrix::Display(){ for(int i=0;i<rows;i++){ for(int j=0;j<columns;j++) cout << (*this)(i,j) << " "; cout << endl; } } Matrix::~Matrix() { delete matrix; } My main program runs: PreProcess test1(argv[1],argv[2]); //test1.SortedOrder(); Matrix test(10,10); test.Display(); And when I run this with the input line uncommented I get: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1371727776 32698 -1 0 0 0 0 0 6332656 0 -1 -1 0 0 6332672 0 0 0 0 0 0 0 0 0 0 0 0 0 -1371732704 32698 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 I really don't have a clue what's going on in memory to cause this, on a side note if I replace memset with: for(int i=0;i<rows*columns;i++) *(matrix+i) &= 0x0; Then it works perfectly, it also works if I don't open the file. If it helps I'm running GCC 64-bit version 4.2.4 on Ubuntu.I assume there's some functionality of memset that I'm not properly understanding.

  Read the article

• A* (A-star) implementation in AS3

  - by Bryan Hare

  Hey, I am putting together a project for a class that requires me to put AI in a top down Tactical Strategy game in Flash AS3. I decided that I would use a node based path finding approach because the game is based on a circular movement scheme. When a player moves a unit he essentially draws a series of line segments that connect that a player unit will follow along. I am trying to put together a similar operation for the AI units in our game by creating a list of nodes to traverse to a target node. Hence my use of Astar (the resulting path can be used to create this line). Here is my Algorithm function findShortestPath (startN:node, goalN:node) { var openSet:Array = new Array(); var closedSet:Array = new Array(); var pathFound:Boolean = false; startN.g_score = 0; startN.h_score = distFunction(startN,goalN); startN.f_score = startN.h_score; startN.fromNode = null; openSet.push (startN); var i:int = 0 for(i= 0; i< nodeArray.length; i++) { for(var j:int =0; j<nodeArray[0].length; j++) { if(!nodeArray[i][j].isPathable) { closedSet.push(nodeArray[i][j]); } } } while (openSet.length != 0) { var cNode:node = openSet.shift(); if (cNode == goalN) { resolvePath (cNode); return true; } closedSet.push (cNode); for (i= 0; i < cNode.dirArray.length; i++) { var neighborNode:node = cNode.nodeArray[cNode.dirArray[i]]; if (!(closedSet.indexOf(neighborNode) == -1)) { continue; } neighborNode.fromNode = cNode; var tenativeg_score:Number = cNode.gscore + distFunction(neighborNode.fromNode,neighborNode); if (openSet.indexOf(neighborNode) == -1) { neighborNode.g_score = neighborNode.fromNode.g_score + distFunction(neighborNode,cNode); if (cNode.dirArray[i] >= 4) { neighborNode.g_score -= 4; } neighborNode.h_score=distFunction(neighborNode,goalN); neighborNode.f_score=neighborNode.g_score+neighborNode.h_score; insertIntoPQ (neighborNode, openSet); //trace(" F Score of neighbor: " + neighborNode.f_score + " H score of Neighbor: " + neighborNode.h_score + " G_score or neighbor: " +neighborNode.g_score); } else if (tenativeg_score <= neighborNode.g_score) { neighborNode.fromNode=cNode; neighborNode.g_score=cNode.g_score+distFunction(neighborNode,cNode); if (cNode.dirArray[i]>=4) { neighborNode.g_score-=4; } neighborNode.f_score=neighborNode.g_score+neighborNode.h_score; openSet.splice (openSet.indexOf(neighborNode),1); //trace(" F Score of neighbor: " + neighborNode.f_score + " H score of Neighbor: " + neighborNode.h_score + " G_score or neighbor: " +neighborNode.g_score); insertIntoPQ (neighborNode, openSet); } } } trace ("fail"); return false; } Right now this function creates paths that are often not optimal or wholly inaccurate given the target and this generally happens when I have nodes that are not path able, and I am not quite sure what I am doing wrong right now. If someone could help me correct this I would appreciate it greatly. Some Notes My OpenSet is essentially a Priority Queue, so thats how I sort my nodes by cost. Here is that function function insertIntoPQ (iNode:node, pq:Array) { var inserted:Boolean=true; var iterater:int=0; while (inserted) { if (iterater==pq.length) { pq.push (iNode); inserted=false; } else if (pq[iterater].f_score >= iNode.f_score) { pq.splice (iterater,0,iNode); inserted=false; } ++iterater; } } Thanks!

  Read the article

• I don't understand how work call_once

  - by SABROG

  Please help me understand how work call_once Here is thread-safe code. I don't understand why this need Thread Local Storage and global_epoch variables. Variable _fast_pthread_once_per_thread_epoch can be changed to constant/enum like {FAST_PTHREAD_ONCE_INIT, BEING_INITIALIZED, FINISH_INITIALIZED}. Why needed count calls in global_epoch? I think this code can be rewriting with logc: if flag FINISH_INITIALIZED do nothing, else go to block with mutexes and this all. #ifndef FAST_PTHREAD_ONCE_H #define FAST_PTHREAD_ONCE_H #include #include typedef sig_atomic_t fast_pthread_once_t; #define FAST_PTHREAD_ONCE_INIT SIG_ATOMIC_MAX extern __thread fast_pthread_once_t _fast_pthread_once_per_thread_epoch; #ifdef __cplusplus extern "C" { #endif extern void fast_pthread_once( pthread_once_t *once, void (*func)(void) ); inline static void fast_pthread_once_inline( fast_pthread_once_t *once, void (*func)(void) ) { fast_pthread_once_t x = *once; /* unprotected access */ if ( x _fast_pthread_once_per_thread_epoch ) { fast_pthread_once( once, func ); } } #ifdef __cplusplus } #endif #endif FAST_PTHREAD_ONCE_H Source fast_pthread_once.c The source is written in C. The lines of the primary function are numbered for reference in the subsequent correctness argument. #include "fast_pthread_once.h" #include static pthread_mutex_t mu = PTHREAD_MUTEX_INITIALIZER; /* protects global_epoch and all fast_pthread_once_t writes */ static pthread_cond_t cv = PTHREAD_COND_INITIALIZER; /* signalled whenever a fast_pthread_once_t is finalized */ #define BEING_INITIALIZED (FAST_PTHREAD_ONCE_INIT - 1) static fast_pthread_once_t global_epoch = 0; /* under mu */ __thread fast_pthread_once_t _fast_pthread_once_per_thread_epoch; static void check( int x ) { if ( x == 0 ) abort(); } void fast_pthread_once( fast_pthread_once_t *once, void (*func)(void) ) { /*01*/ fast_pthread_once_t x = *once; /* unprotected access */ /*02*/ if ( x _fast_pthread_once_per_thread_epoch ) { /*03*/ check( pthread_mutex_lock(µ) == 0 ); /*04*/ if ( *once == FAST_PTHREAD_ONCE_INIT ) { /*05*/ *once = BEING_INITIALIZED; /*06*/ check( pthread_mutex_unlock(µ) == 0 ); /*07*/ (*func)(); /*08*/ check( pthread_mutex_lock(µ) == 0 ); /*09*/ global_epoch++; /*10*/ *once = global_epoch; /*11*/ check( pthread_cond_broadcast(&cv;) == 0 ); /*12*/ } else { /*13*/ while ( *once == BEING_INITIALIZED ) { /*14*/ check( pthread_cond_wait(&cv;, µ) == 0 ); /*15*/ } /*16*/ } /*17*/ _fast_pthread_once_per_thread_epoch = global_epoch; /*18*/ check (pthread_mutex_unlock(µ) == 0); } } This code from BOOST: #ifndef BOOST_THREAD_PTHREAD_ONCE_HPP #define BOOST_THREAD_PTHREAD_ONCE_HPP // once.hpp // // (C) Copyright 2007-8 Anthony Williams // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) #include #include #include #include "pthread_mutex_scoped_lock.hpp" #include #include #include namespace boost { struct once_flag { boost::uintmax_t epoch; }; namespace detail { BOOST_THREAD_DECL boost::uintmax_t& get_once_per_thread_epoch(); BOOST_THREAD_DECL extern boost::uintmax_t once_global_epoch; BOOST_THREAD_DECL extern pthread_mutex_t once_epoch_mutex; BOOST_THREAD_DECL extern pthread_cond_t once_epoch_cv; } #define BOOST_ONCE_INITIAL_FLAG_VALUE 0 #define BOOST_ONCE_INIT {BOOST_ONCE_INITIAL_FLAG_VALUE} // Based on Mike Burrows fast_pthread_once algorithm as described in // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2444.html template void call_once(once_flag& flag,Function f) { static boost::uintmax_t const uninitialized_flag=BOOST_ONCE_INITIAL_FLAG_VALUE; static boost::uintmax_t const being_initialized=uninitialized_flag+1; boost::uintmax_t const epoch=flag.epoch; boost::uintmax_t& this_thread_epoch=detail::get_once_per_thread_epoch(); if(epoch #endif I right understand, boost don't use atomic operation, so code from boost not thread-safe?

  Read the article

• Why does my finite state machine take so long to execute?

  - by BillyONeal

  Hello all :) I'm working on a state machine which is supposed to extract function calls of the form /* I am a comment */ //I am a comment perf("this.is.a.string.which\"can have QUOTES\"", 123456); where the extracted data would be perf("this.is.a.string.which\"can have QUOTES\"", 123456); from a file. Currently, to process a 41kb file, this process is taking close to a minute and a half. Is there something I'm seriously misunderstanding here about this finite state machine? #include <boost/algorithm/string.hpp> std::vector<std::string> Foo() { std::string fileData; //Fill filedata with the contents of a file std::vector<std::string> results; std::string::iterator begin = fileData.begin(); std::string::iterator end = fileData.end(); std::string::iterator stateZeroFoundLocation = fileData.begin(); std::size_t state = 0; for(; begin < end; begin++) { switch (state) { case 0: if (boost::starts_with(boost::make_iterator_range(begin, end), "pref(")) { stateZeroFoundLocation = begin; begin += 4; state = 2; } else if (*begin == '/') state = 1; break; case 1: state = 0; switch (*begin) { case '*': begin = boost::find_first(boost::make_iterator_range(begin, end), "*/").end(); break; case '/': begin = std::find(begin, end, L'\n'); } break; case 2: if (*begin == '"') state = 3; break; case 3: switch(*begin) { case '\\': state = 4; break; case '"': state = 5; } break; case 4: state = 3; break; case 5: if (*begin == ',') state = 6; break; case 6: if (*begin != ' ') state = 7; break; case 7: switch(*begin) { case '"': state = 8; break; default: state = 10; break; } break; case 8: switch(*begin) { case '\\': state = 9; break; case '"': state = 10; } break; case 9: state = 8; break; case 10: if (*begin == ')') state = 11; break; case 11: if (*begin == ';') state = 12; break; case 12: state = 0; results.push_back(std::string(stateZeroFoundLocation, begin)); }; } return results; } Billy3

  Read the article

• push_back of STL list got bad performance?

  - by Leon Zhang

  I wrote a simple program to test STL list performance against a simple C list-like data structure. It shows bad performance at "push_back()" line. Any comments on it? $ ./test2 Build the type list : time consumed -> 0.311465 Iterate over all items: time consumed -> 0.00898 Build the simple C List: time consumed -> 0.020275 Iterate over all items: time consumed -> 0.008755 The source code is: #include <stdexcept> #include "high_resolution_timer.hpp" #include <list> #include <algorithm> #include <iostream> #define TESTNUM 1000000 /* The test struct */ struct MyType { int num; }; /* * C++ STL::list Test */ typedef struct MyType* mytype_t; void myfunction(mytype_t t) { } int test_stl_list() { std::list<mytype_t> mylist; util::high_resolution_timer t; /* * Build the type list */ t.restart(); for(int i = 0; i < TESTNUM; i++) { mytype_t aItem = (mytype_t) malloc(sizeof(struct MyType)); if(aItem == NULL) { printf("Error: while malloc\n"); return -1; } aItem->num = i; mylist.push_back(aItem); } std::cout << " Build the type list : time consumed -> " << t.elapsed() << std::endl; /* * Iterate over all item */ t.restart(); std::for_each(mylist.begin(), mylist.end(), myfunction); std::cout << " Iterate over all items: time consumed -> " << t.elapsed() << std::endl; return 0; } /* * a simple C list */ struct MyCList; struct MyCList{ struct MyType m; struct MyCList* p_next; }; int test_simple_c_list() { struct MyCList* p_list_head = NULL; util::high_resolution_timer t; /* * Build it */ t.restart(); struct MyCList* p_new_item = NULL; for(int i = 0; i < TESTNUM; i++) { p_new_item = (struct MyCList*) malloc(sizeof(struct MyCList)); if(p_new_item == NULL) { printf("ERROR : while malloc\n"); return -1; } p_new_item->m.num = i; p_new_item->p_next = p_list_head; p_list_head = p_new_item; } std::cout << " Build the simple C List: time consumed -> " << t.elapsed() << std::endl; /* * Iterate all items */ t.restart(); p_new_item = p_list_head; while(p_new_item->p_next != NULL) { p_new_item = p_new_item->p_next; } std::cout << " Iterate over all items: time consumed -> " << t.elapsed() << std::endl; return 0; } int main(int argc, char** argv) { if(test_stl_list() != 0) { printf("ERROR: error at testcase1\n"); return -1; } if(test_simple_c_list() != 0) { printf("ERROR: error at testcase2\n"); return -1; } return 0; }

  Read the article

• Astar implementation in AS3

  - by Bryan Hare

  Hey, I am putting together a project for a class that requires me to put AI in a top down Tactical Strategy game in Flash AS3. I decided that I would use a node based path finding approach because the game is based on a circular movement scheme. When a player moves a unit he essentially draws a series of line segments that connect that a player unit will follow along. I am trying to put together a similar operation for the AI units in our game by creating a list of nodes to traverse to a target node. Hence my use of Astar (the resulting path can be used to create this line). Here is my Algorithm function findShortestPath (startN:node, goalN:node) { var openSet:Array = new Array(); var closedSet:Array = new Array(); var pathFound:Boolean = false; startN.g_score = 0; startN.h_score = distFunction(startN,goalN); startN.f_score = startN.h_score; startN.fromNode = null; openSet.push (startN); var i:int = 0 for(i= 0; i< nodeArray.length; i++) { for(var j:int =0; j<nodeArray[0].length; j++) { if(!nodeArray[i][j].isPathable) { closedSet.push(nodeArray[i][j]); } } } while (openSet.length != 0) { var cNode:node = openSet.shift(); if (cNode == goalN) { resolvePath (cNode); return true; } closedSet.push (cNode); for (i= 0; i < cNode.dirArray.length; i++) { var neighborNode:node = cNode.nodeArray[cNode.dirArray[i]]; if (!(closedSet.indexOf(neighborNode) == -1)) { continue; } neighborNode.fromNode = cNode; var tenativeg_score:Number = cNode.gscore + distFunction(neighborNode.fromNode,neighborNode); if (openSet.indexOf(neighborNode) == -1) { neighborNode.g_score = neighborNode.fromNode.g_score + distFunction(neighborNode,cNode); if (cNode.dirArray[i] >= 4) { neighborNode.g_score -= 4; } neighborNode.h_score=distFunction(neighborNode,goalN); neighborNode.f_score=neighborNode.g_score+neighborNode.h_score; insertIntoPQ (neighborNode, openSet); //trace(" F Score of neighbor: " + neighborNode.f_score + " H score of Neighbor: " + neighborNode.h_score + " G_score or neighbor: " +neighborNode.g_score); } else if (tenativeg_score <= neighborNode.g_score) { neighborNode.fromNode=cNode; neighborNode.g_score=cNode.g_score+distFunction(neighborNode,cNode); if (cNode.dirArray[i]>=4) { neighborNode.g_score-=4; } neighborNode.f_score=neighborNode.g_score+neighborNode.h_score; openSet.splice (openSet.indexOf(neighborNode),1); //trace(" F Score of neighbor: " + neighborNode.f_score + " H score of Neighbor: " + neighborNode.h_score + " G_score or neighbor: " +neighborNode.g_score); insertIntoPQ (neighborNode, openSet); } } } trace ("fail"); return false; } Right now this function creates paths that are often not optimal or wholly inaccurate given the target and this generally happens when I have nodes that are not path able, and I am not quite sure what I am doing wrong right now. If someone could help me correct this I would appreciate it greatly. Some Notes My OpenSet is essentially a Priority Queue, so thats how I sort my nodes by cost. Here is that function function insertIntoPQ (iNode:node, pq:Array) { var inserted:Boolean=true; var iterater:int=0; while (inserted) { if (iterater==pq.length) { pq.push (iNode); inserted=false; } else if (pq[iterater].f_score >= iNode.f_score) { pq.splice (iterater,0,iNode); inserted=false; } ++iterater; } } Thanks!

  Read the article

• Calculate new position of player

  - by user1439111

  Edit: I will summerize my question since it is very long (Thanks Len for pointing it out) What I'm trying to find out is to get a new position of a player after an X amount of time. The following variables are known: - Speed - Length between the 2 points - Source position (X, Y) - Destination position (X, Y) How can I calculate a position between the source and destion with these variables given? For example: source: 0, 0 destination: 10, 0 speed: 1 so after 1 second the players position would be 1, 0 The code below works but it's quite long so I'm looking for something shorter/more logical ====================================================================== I'm having a hard time figuring out how to calculate a new position of a player ingame. This code is server sided used to track a player(It's a emulator so I don't have access to the clients code). The collision detection of the server works fine I'm using bresenham's line algorithm and a raycast to determine at which point a collision happens. Once I deteremined the collision I calculate the length of the path the player is about to walk and also the total time. I would like to know the new position of a player each second. This is the code I'm currently using. It's in C++ but I am porting the server to C# and I haven't written the code in C# yet. // Difference between the source X - destination X //and source y - destionation Y float xDiff, yDiff; xDiff = xDes - xSrc; yDiff = yDes - ySrc; float walkingLength = 0.00F; float NewX = xDiff * xDiff; float NewY = yDiff * yDiff; walkingLength = NewX + NewY; walkingLength = sqrt(walkingLength); const float PI = 3.14159265F; float Angle = 0.00F; if(xDes >= xSrc && yDes >= ySrc) { Angle = atanf((yDiff / xDiff)); Angle = Angle * 180 / PI; } else if(xDes < xSrc && yDes >= ySrc) { Angle = atanf((-xDiff / yDiff)); Angle = Angle * 180 / PI; Angle += 90.00F; } else if(xDes < xSrc && yDes < ySrc) { Angle = atanf((yDiff / xDiff)); Angle = Angle * 180 / PI; Angle += 180.00F; } else if(xDes >= xSrc && yDes < ySrc) { Angle = atanf((xDiff / -yDiff)); Angle = Angle * 180 / PI; Angle += 270.00F; } float WalkingTime = (float)walkingLength / (float)speed; bool Done = false; float i = 0; while(i < walkingLength) { if(Done == true) { break; } if(WalkingTime >= 1000) { Sleep(1000); i += speed; WalkTime -= 1000; } else { Sleep(WalkTime); i += speed * WalkTime; WalkTime -= 1000; Done = true; } if(Angle >= 0 && Angle < 90) { float xNew = cosf(Angle * PI / 180) * i; float yNew = sinf(Angle * PI / 180) * i; float NewCharacterX = xSrc + xNew; float NewCharacterY = ySrc + yNew; } I have cut the last part of the loop since it's just 3 other else if statements with 3 other angle conditions and the only change is the sin and cos. The given speed parameter is the speed/second. The code above works but as you can see it's quite long so I'm looking for a new way to calculate this. btw, don't mind the while loop to calculate each new position I'm going to use a timer in C# Thank you very much

  Read the article

• Dynamically specify the type in C#

  - by Lirik

  I'm creating a custom DataSet and I'm under some constrains: I want the user to specify the type of the data which they want to store. I want to reduce type-casting because I think it will be VERY expensive. I will use the data VERY frequently in my application. I don't know what type of data will be stored in the DataSet, so my initial idea was to make it a List of objects, but I suspect that the frequent use of the data and the need to type-cast will be very expensive. The basic idea is this: class DataSet : IDataSet { private Dictionary<string, List<Object>> _data; /// <summary> /// Constructs the data set given the user-specified labels. /// </summary> /// <param name="labels"> /// The labels of each column in the data set. /// </param> public DataSet(List<string> labels) { _data = new Dictionary<string, List<object>>(); foreach (string label in labels) { _data.Add(label, new List<object>()); } } #region IDataSet Members public List<string> DataLabels { get { return _data.Keys.ToList(); } } public int Count { get { _data[_data.Keys[0]].Count; } } public List<object> GetValues(string label) { return _data[label]; } public object GetValue(string label, int index) { return _data[label][index]; } public void InsertValue(string label, object value) { _data[label].Insert(0, value); } public void AddValue(string label, object value) { _data[label].Add(value); } #endregion } A concrete example where the DataSet will be used is to store data obtained from a CSV file where the first column contains the labels. When the data is being loaded from the CSV file I'd like to specify the type rather than casting to object. The data could contain columns such as dates, numbers, strings, etc. Here is what it could look like: "Date","Song","Rating","AvgRating","User" "02/03/2010","Code Monkey",4.6,4.1,"joe" "05/27/2009","Code Monkey",1.2,4.5,"jill" The data will be used in a Machine Learning/Artificial Intelligence algorithm, so it is essential that I make the reading of data very fast. I want to eliminate type-casting as much as possible, since I can't afford to cast from 'object' to whatever data type is needed on every read. I've seen applications that allow the user to pick the specific data type for each item in the csv file, so I'm trying to make a similar solution where a different type can be specified for each column. I want to create a generic solution so I don't have to return a List<object> but a List<DateTime> (if it's a DateTime column) or List<double> (if it's a column of doubles). Is there any way that this can be achieved? Perhaps my approach is wrong, is there a better approach to this problem?

  Read the article

• help setting up an IPSEC vpn from my linux box

  - by robthewolf

  I have an office with a router and a remote server (Linux - Ubuntu 10.10). Both locations need to connect to a data supplier through a VPN. The VPN is an IPSEC gateway. I was able to configure my Linksys rv42 router to create a VPN connection successfully and now I need to do the same for Linux server. I have been messing around with this for too long. First I tried OpenVPN, but that is SSL and not IPSEC. Then I tried Shrew. I think I have the settings correct but I haven't been able to create the connection. It maybe that I have to use something else like a direct IPSEC config or something like that. If someone knows of a way to turn the following settings that I have been given below into a working IPSEC VPN connection I would be very grateful. Here are the settings I was given that must be used to connect to my supplier: Local destination network: 192.168.4.0/24 Local destination hosts: 192.168.4.100 Remote destination network: 192.167.40.0/24 Remote destination hosts: 192.168.40.27 VPN peering point: xxx.xxx.xxx.xxx Then they have given me the following details: IPSEC/ISAKMP Phase 1 Parameters: Authentication method: pre shared secret Diffie Hellman group: group 2 Encryption Algorithm: 3DES Lifetime in seconds:28800 Phase 2 parameters: IPSEC security: ESP Encryption algortims: 3DES Authentication algorithms: MD5 lifetime in seconds: 28800 pfs: disabled Here are the settings from my attempt to use shrew: n:version:2 n:network-ike-port:500 n:network-mtu-size:1380 n:client-addr-auto:0 n:network-frag-size:540 n:network-dpd-enable:1 n:network-notify-enable:1 n:client-banner-enable:1 n:client-dns-used:1 b:auth-mutual-psk:YjJzN2QzdDhyN2EyZDNpNG42ZzQ= n:phase1-dhgroup:2 n:phase1-keylen:0 n:phase1-life-secs:28800 n:phase1-life-kbytes:0 n:vendor-chkpt-enable:0 n:phase2-keylen:0 n:phase2-pfsgroup:-1 n:phase2-life-secs:28800 n:phase2-life-kbytes:0 n:policy-nailed:0 n:policy-list-auto:1 n:client-dns-auto:1 n:network-natt-port:4500 n:network-natt-rate:15 s:client-dns-addr:0.0.0.0 s:client-dns-suffix: s:network-host:xxx.xxx.xxx.xxx s:client-auto-mode:pull s:client-iface:virtual s:client-ip-addr:192.168.4.0 s:client-ip-mask:255.255.255.0 s:network-natt-mode:enable s:network-frag-mode:disable s:auth-method:mutual-psk s:ident-client-type:address s:ident-client-data:192.168.4.0 s:ident-server-type:address s:ident-server-data:192.168.40.0 s:phase1-exchange:aggressive s:phase1-cipher:3des s:phase1-hash:md5 s:phase2-transform:3des s:phase2-hmac:md5 s:ipcomp-transform:disabled Finally here is the debug output from the shrew log: 10/12/22 17:22:18 ii : ipc client process thread begin ... 10/12/22 17:22:18 < A : peer config add message 10/12/22 17:22:18 DB : peer added ( obj count = 1 ) 10/12/22 17:22:18 ii : local address 217.xxx.xxx.xxx selected for peer 10/12/22 17:22:18 DB : tunnel added ( obj count = 1 ) 10/12/22 17:22:18 < A : proposal config message 10/12/22 17:22:18 < A : proposal config message 10/12/22 17:22:18 < A : client config message 10/12/22 17:22:18 < A : local id '192.168.4.0' message 10/12/22 17:22:18 < A : remote id '192.168.40.0' message 10/12/22 17:22:18 < A : preshared key message 10/12/22 17:22:18 < A : peer tunnel enable message 10/12/22 17:22:18 DB : new phase1 ( ISAKMP initiator ) 10/12/22 17:22:18 DB : exchange type is aggressive 10/12/22 17:22:18 DB : 217.xxx.xxx.xxx:500 <- 206.xxx.xxx.xxx:500 10/12/22 17:22:18 DB : c1a8b31ac860995d:0000000000000000 10/12/22 17:22:18 DB : phase1 added ( obj count = 1 ) 10/12/22 17:22:18 : security association payload 10/12/22 17:22:18 : - proposal #1 payload 10/12/22 17:22:18 : -- transform #1 payload 10/12/22 17:22:18 : key exchange payload 10/12/22 17:22:18 : nonce payload 10/12/22 17:22:18 : identification payload 10/12/22 17:22:18 : vendor id payload 10/12/22 17:22:18 ii : local supports nat-t ( draft v00 ) 10/12/22 17:22:18 : vendor id payload 10/12/22 17:22:18 ii : local supports nat-t ( draft v01 ) 10/12/22 17:22:18 : vendor id payload 10/12/22 17:22:18 ii : local supports nat-t ( draft v02 ) 10/12/22 17:22:18 : vendor id payload 10/12/22 17:22:18 ii : local supports nat-t ( draft v03 ) 10/12/22 17:22:18 : vendor id payload 10/12/22 17:22:18 ii : local supports nat-t ( rfc ) 10/12/22 17:22:18 : vendor id payload 10/12/22 17:22:18 ii : local supports DPDv1 10/12/22 17:22:18 : vendor id payload 10/12/22 17:22:18 ii : local is SHREW SOFT compatible 10/12/22 17:22:18 : vendor id payload 10/12/22 17:22:18 ii : local is NETSCREEN compatible 10/12/22 17:22:18 : vendor id payload 10/12/22 17:22:18 ii : local is SIDEWINDER compatible 10/12/22 17:22:18 : vendor id payload 10/12/22 17:22:18 ii : local is CISCO UNITY compatible 10/12/22 17:22:18 = : cookies c1a8b31ac860995d:0000000000000000 10/12/22 17:22:18 = : message 00000000 10/12/22 17:22:18 - : send IKE packet 217.xxx.xxx.xxx:500 - 206.xxx.xxx.xxx:500 ( 484 bytes ) 10/12/22 17:22:18 DB : phase1 resend event scheduled ( ref count = 2 ) 10/12/22 17:22:18 ii : opened tap device tap0 10/12/22 17:22:28 - : resend 1 phase1 packet(s) 217.xxx.xxx.xxx:500 - 206.xxx.xxx.xxx:500 10/12/22 17:22:38 - : resend 1 phase1 packet(s) 217.xxx.xxx.xxx:500 - 206.xxx.xxx.xxx:500 10/12/22 17:22:48 - : resend 1 phase1 packet(s) 217.xxx.xxx.xxx:500 - 206.xxx.xxx.xxx:500 10/12/22 17:22:58 ii : resend limit exceeded for phase1 exchange 10/12/22 17:22:58 ii : phase1 removal before expire time 10/12/22 17:22:58 DB : phase1 deleted ( obj count = 0 ) 10/12/22 17:22:58 ii : closed tap device tap0 10/12/22 17:22:58 DB : tunnel stats event canceled ( ref count = 1 ) 10/12/22 17:22:58 DB : removing tunnel config references 10/12/22 17:22:58 DB : removing tunnel phase2 references 10/12/22 17:22:58 DB : removing tunnel phase1 references 10/12/22 17:22:58 DB : tunnel deleted ( obj count = 0 ) 10/12/22 17:22:58 DB : removing all peer tunnel refrences 10/12/22 17:22:58 DB : peer deleted ( obj count = 0 ) 10/12/22 17:22:58 ii : ipc client process thread exit ...

  Read the article

• Slicing a time range into parts

  - by beporter

  First question. Be gentle. I'm working on software that tracks technicians' time spent working on tasks. The software needs to be enhanced to recognize different billable rate multipliers based on the day of the week and the time of day. (For example, "Time and a half after 5 PM on weekdays.") The tech using the software is only required to log the date, his start time and his stop time (in hours and minutes). The software is expected to break the time entry into parts at the boundaries of when the rate multipliers change. A single time entry is not permitted to span multiple days. Here is a partial sample of the rate table. The first-level array keys are the days of the week, obviously. The second-level array keys represent the time of the day when the new multiplier kicks in, and runs until the next sequential entry in the array. The array values are the multiplier for that time range. [rateTable] => Array ( [Monday] => Array ( [00:00:00] => 1.5 [08:00:00] => 1 [17:00:00] => 1.5 [23:59:59] => 1 ) [Tuesday] => Array ( [00:00:00] => 1.5 [08:00:00] => 1 [17:00:00] => 1.5 [23:59:59] => 1 ) ... ) In plain English, this represents a time-and-a-half rate from midnight to 8 am, regular rate from 8 to 5 pm, and time-and-a-half again from 5 till 11:59 pm. The time that these breaks occur may be arbitrary to the second and there can be an arbitrary number of them for each day. (This format is entirely negotiable, but my goal is to make it as easily human-readable as possible.) As an example: a time entry logged on Monday from 15:00:00 (3 PM) to 21:00:00 (9 PM) would consist of 2 hours billed at 1x and 4 hours billed at 1.5x. It is also possible for a single time entry to span multiple breaks. Using the example rateTable above, a time entry from 6 AM to 9 PM would have 3 sub-ranges from 6-8 AM @ 1.5x, 8AM-5PM @ 1x, and 5-9 PM @ 1.5x. By contrast, it's also possible that a time entry may only be from 08:15:00 to 08:30:00 and be entirely encompassed in the range of a single multiplier. I could really use some help coding up some PHP (or at least devising an algorithm) that can take a day of the week, a start time and a stop time and parse into into the required subparts. It would be ideal to have the output be an array that consists of multiple entries for a (start,stop,multiplier) triplet. For the above example, the output would be: [output] => Array ( [0] => Array ( [start] => 15:00:00 [stop] => 17:00:00 [multiplier] => 1 ) [1] => Array ( [start] => 17:00:00 [stop] => 21:00:00 [multiplier] => 1.5 ) ) I just plain can't wrap my head around the logic of splitting a single (start,stop) into (potentially) multiple subparts.

  Read the article

• Choosing a type for search results in C#

  - by Chris M

  I have a result set that will never exceed 500; the results that come back from the web-service are assigned to a search results object. The data from the webservice is about 2mb; the bit I want to use is about a third of each record, so this allows me to cache and quickly manipulate it. I want to be able to sort and filter the results with the least amount of overhead and as fast as possible so I used the VCSKICKS timing class to measure their performance Average Total (10,000) Type Create Sort Create Sort HashSet 0.1579 0.0003 1579 3 IList 0.0633 0.0002 633 2 IQueryable 0.0072 0.0432 72 432 Measured in Seconds using http://www.vcskicks.com/algorithm-performance.php I created the hashset through a for loop over the web-service response (adding to the hashset). The List & IQueryable were created using LINQ. Question I can understand why HashSet takes longer to create (the foreach loop vs linq); but why would IQueryable take longer to sort than the other two; and finally is there a better way to assign the HashSet. Thanks Actual Program public class Program { private static AuthenticationHeader _authHeader; private static OPSoapClient _opSession; private static AccommodationSearchResponse _searchResults; private static HashSet<SearchResults> _myHash; private static IList<SearchResults> _myList; private static IQueryable<SearchResults> _myIQuery; static void Main(string[] args) { #region Setup WebService _authHeader = new AuthenticationHeader { UserName = "xx", Password = "xx" }; _opSession = new OPSoapClient(); #region Setup Search Results _searchResults = _opgSession.SearchCR(_authHeader, "ENG", "GBP", "GBR"); #endregion Setup Search Results #endregion Setup WebService // HASHSET SpeedTester hashTest = new SpeedTester(TestHashSet); hashTest.RunTest(); Console.WriteLine("- Hash Test \nAverage Running Time: {0}; Total Time: {1}", hashTest.AverageRunningTime, hashTest.TotalRunningTime); SpeedTester hashSortTest = new SpeedTester(TestSortingHashSet); hashSortTest.RunTest(); Console.WriteLine("- Hash Sort Test \nAverage Running Time: {0}; Total Time: {1}", hashSortTest.AverageRunningTime, hashSortTest.TotalRunningTime); // ILIST SpeedTester listTest = new SpeedTester(TestList); listTest.RunTest(); Console.WriteLine("- List Test \nAverage Running Time: {0}; Total Time: {1}", listTest.AverageRunningTime, listTest.TotalRunningTime); SpeedTester listSortTest = new SpeedTester(TestSortingList); listSortTest.RunTest(); Console.WriteLine("- List Sort Test \nAverage Running Time: {0}; Total Time: {1}", listSortTest.AverageRunningTime, listSortTest.TotalRunningTime); // IQUERIABLE SpeedTester iqueryTest = new SpeedTester(TestIQueriable); iqueryTest.RunTest(); Console.WriteLine("- iquery Test \nAverage Running Time: {0}; Total Time: {1}", iqueryTest.AverageRunningTime, iqueryTest.TotalRunningTime); SpeedTester iquerySortTest = new SpeedTester(TestSortableIQueriable); iquerySortTest.RunTest(); Console.WriteLine("- iquery Sort Test \nAverage Running Time: {0}; Total Time: {1}", iquerySortTest.AverageRunningTime, iquerySortTest.TotalRunningTime); } static void TestHashSet() { var test = _searchResults.Items; _myHash = new HashSet<SearchResults>(); foreach(var x in test) { _myHash.Add(new SearchResults { Ref = x.Ref, Price = x.StandardPrice }); } } static void TestSortingHashSet() { var sorted = _myHash.OrderBy(s => s.Price); } static void TestList() { var test = _searchResults.Items; _myList = (from x in test select new SearchResults { Ref = x.Ref, Price = x.StandardPrice }).ToList(); } static void TestSortingList() { var sorted = _myList.OrderBy(s => s.Price); } static void TestIQueriable() { var test = _searchResults.Items; _myIQuery = (from x in test select new SearchResults { Ref = x.Ref, Price = x.StandardPrice }).AsQueryable(); } static void TestSortableIQueriable() { var sorted = _myIQuery.OrderBy(s => s.Price); } }

  Read the article

• Picking good first estimates for Goldschmidt division

  - by Mads Elvheim

  I'm calculating fixedpoint reciprocals in Q22.10 with Goldschmidt division for use in my software rasterizer on ARM. This is done by just setting the nominator to 1, i.e the nominator becomes the scalar on the first iteration. To be honest, I'm kind of following the wikipedia algorithm blindly here. The article says that if the denominator is scaled in the half-open range (0.5, 1.0], a good first estimate can be based on the denominator alone: Let F be the estimated scalar and D be the denominator, then F = 2 - D. But when doing this, I lose a lot of precision. Say if I want to find the reciprocal of 512.00002f. In order to scale the number down, I lose 10 bits of precision in the fraction part, which is shifted out. So, my questions are: Is there a way to pick a better estimate which does not require normalization? Also, is it possible to pre-calculate the first estimates so the series converges faster? Right now, it converges after the 4th iteration on average. On ARM this is about ~50 cycles worst case, and that's not taking emulation of clz/bsr into account, nor memory lookups. Here is my testcase. Note: The software implementation of clz on line 13 is from my post here. You can replace it with an intrinsic if you want. #include <stdio.h> #include <stdint.h> const unsigned int BASE = 22ULL; static unsigned int divfp(unsigned int val, int* iter) { /* Nominator, denominator, estimate scalar and previous denominator */ unsigned long long N,D,F, DPREV; int bitpos; *iter = 1; D = val; /* Get the shift amount + is right-shift, - is left-shift. */ bitpos = 31 - clz(val) - BASE; /* Normalize into the half-range (0.5, 1.0] */ if(0 < bitpos) D >>= bitpos; else D <<= (-bitpos); /* (FNi / FDi) == (FN(i+1) / FD(i+1)) */ /* F = 2 - D */ F = (2ULL<<BASE) - D; /* N = F for the first iteration, because the nominator is simply 1. So don't waste a 64-bit UMULL on a multiply with 1 */ N = F; D = ((unsigned long long)D*F)>>BASE; while(1){ DPREV = D; F = (2<<(BASE)) - D; D = ((unsigned long long)D*F)>>BASE; /* Bail when we get the same value for two denominators in a row. This means that the error is too small to make any further progress. */ if(D == DPREV) break; N = ((unsigned long long)N*F)>>BASE; *iter = *iter + 1; } if(0 < bitpos) N >>= bitpos; else N <<= (-bitpos); return N; } int main(int argc, char* argv[]) { double fv, fa; int iter; unsigned int D, result; sscanf(argv[1], "%lf", &fv); D = fv*(double)(1<<BASE); result = divfp(D, &iter); fa = (double)result / (double)(1UL << BASE); printf("Value: %8.8lf 1/value: %8.8lf FP value: 0x%.8X\n", fv, fa, result); printf("iteration: %d\n",iter); return 0; }

  Read the article

• Why is processing a sorted array faster than an unsorted array?

  - by GManNickG

  Here is a piece of code that shows some very peculiar performance. For some strange reason, sorting the data miraculously speeds up the code by almost 6x: #include <algorithm> #include <ctime> #include <iostream> int main() { // generate data const unsigned arraySize = 32768; int data[arraySize]; for (unsigned c = 0; c < arraySize; ++c) data[c] = std::rand() % 256; // !!! with this, the next loop runs faster std::sort(data, data + arraySize); // test clock_t start = clock(); long long sum = 0; for (unsigned i = 0; i < 100000; ++i) { // primary loop for (unsigned c = 0; c < arraySize; ++c) { if (data[c] >= 128) sum += data[c]; } } double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC; std::cout << elapsedTime << std::endl; std::cout << "sum = " << sum << std::endl; } Without std::sort(data, data + arraySize);, the code runs in 11.54 seconds. With the sorted data, the code runs in 1.93 seconds. Initially I thought this might be just a language or compiler anomaly. So I tried it Java... import java.util.Arrays; import java.util.Random; public class Main { public static void main(String[] args) { // generate data int arraySize = 32768; int data[] = new int[arraySize]; Random rnd = new Random(0); for (int c = 0; c < arraySize; ++c) data[c] = rnd.nextInt() % 256; // !!! with this, the next loop runs faster Arrays.sort(data); // test long start = System.nanoTime(); long sum = 0; for (int i = 0; i < 100000; ++i) { // primary loop for (int c = 0; c < arraySize; ++c) { if (data[c] >= 128) sum += data[c]; } } System.out.println((System.nanoTime() - start) / 1000000000.0); System.out.println("sum = " + sum); } } with a similar but less extreme result. My first thought was that sorting brings the data into cache, but my next thought was how silly that is because the array was just generated. What is going on? Why is a sorted array faster than an unsorted array? The code is summing up some independent terms, the order should not matter.

  Read the article

• gzip compression using varnish cache

  - by Ali Raza

  Im trying to provide gzip compression using varnish cache. But when I set content-encoding as gzip using my below mentioned configuration for varnish (default.vcl). Browser failed to download those content for which i set content-encoding as gzipped. Varnish configuration file: backend default { .host = "127.0.0.1"; .port = "9000"; } backend socketIO { .host = "127.0.0.1"; .port = "8083"; } acl purge { "127.0.0.1"; "192.168.15.0"/24; } sub vcl_fetch { /* If the request is for pictures, javascript, css, etc */ if (req.url ~ "^/public/" || req.url ~ "\.js"){ unset req.http.cookie; set beresp.http.Content-Encoding= "gzip"; set beresp.ttl = 86400s; set beresp.http.Cache-Control = "public, max-age=3600"; /*set the expires time to response header*/ set beresp.http.expires=beresp.ttl; /* marker for vcl_deliver to reset Age: */ set beresp.http.magicmarker = "1"; } if (!beresp.cacheable) { return (pass); } return (deliver); } sub vcl_deliver { if (resp.http.magicmarker) { /* Remove the magic marker */ unset resp.http.magicmarker; /* By definition we have a fresh object */ set resp.http.age = "0"; } if(obj.hits > 0) { set resp.http.X-Varnish-Cache = "HIT"; }else { set resp.http.X-Varnish-Cache = "MISS"; } return (deliver); } sub vcl_recv { if (req.http.x-forwarded-for) { set req.http.X-Forwarded-For = req.http.X-Forwarded-For ", " client.ip; } else { set req.http.X-Forwarded-For = client.ip; } if (req.request != "GET" && req.request != "HEAD" && req.request != "PUT" && req.request != "POST" && req.request != "TRACE" && req.request != "OPTIONS" && req.request != "DELETE") { /* Non-RFC2616 or CONNECT which is weird. */ return (pipe); } # Pass requests that are not GET or HEAD if (req.request != "GET" && req.request != "HEAD") { return(pass); } #pipe websocket connections directly to Node.js if (req.http.Upgrade ~ "(?i)websocket") { set req.backend = socketIO; return (pipe); } # Properly handle different encoding types if (req.http.Accept-Encoding) { if (req.url ~ "\.(jpg|png|gif|gz|tgz|bz2|tbz|mp3|ogg|js|css)$") { # No point in compressing these remove req.http.Accept-Encoding; } elsif (req.http.Accept-Encoding ~ "gzip") { set req.http.Accept-Encoding = "gzip"; } elsif (req.http.Accept-Encoding ~ "deflate") { set req.http.Accept-Encoding = "deflate"; } else { # unkown algorithm remove req.http.Accept-Encoding; } } # allow PURGE from localhost and 192.168.15... if (req.request == "PURGE") { if (!client.ip ~ purge) { error 405 "Not allowed."; } return (lookup); } return (lookup); } sub vcl_hit { if (req.request == "PURGE") { purge_url(req.url); error 200 "Purged."; } } sub vcl_miss { if (req.request == "PURGE") { purge_url(req.url); error 200 "Purged."; } } sub vcl_pipe { if (req.http.upgrade) { set bereq.http.upgrade = req.http.upgrade; } } Response Header: Cache-Control:public, max-age=3600 Connection:keep-alive Content-Encoding:gzip Content-Length:11520 Content-Type:application/javascript Date:Fri, 06 Apr 2012 04:53:41 GMT ETag:"1330493670000--987570445" Last-Modified:Wed, 29 Feb 2012 05:34:30 GMT Server:Play! Framework;1.2.x-localbuild;dev Via:1.1 varnish X-Varnish:118464579 118464571 X-Varnish-Cache:HIT age:0 expires:86400.000 Any suggestion on how to fix it and how to provide gzip compression using varnish.

  Read the article

• STL find performs bettern than hand-crafter loop

  - by dusha

  Hello all, I have some question. Given the following C++ code fragment: #include <boost/progress.hpp> #include <vector> #include <algorithm> #include <numeric> #include <iostream> struct incrementor { incrementor() : curr_() {} unsigned int operator()() { return curr_++; } private: unsigned int curr_; }; template<class Vec> char const* value_found(Vec const& v, typename Vec::const_iterator i) { return i==v.end() ? "no" : "yes"; } template<class Vec> typename Vec::const_iterator find1(Vec const& v, typename Vec::value_type val) { return find(v.begin(), v.end(), val); } template<class Vec> typename Vec::const_iterator find2(Vec const& v, typename Vec::value_type val) { for(typename Vec::const_iterator i=v.begin(), end=v.end(); i<end; ++i) if(*i==val) return i; return v.end(); } int main() { using namespace std; typedef vector<unsigned int>::const_iterator iter; vector<unsigned int> vec; vec.reserve(10000000); boost::progress_timer pt; generate_n(back_inserter(vec), vec.capacity(), incrementor()); //added this line, to avoid any doubts, that compiler is able to // guess the data is sorted random_shuffle(vec.begin(), vec.end()); cout << "value generation required: " << pt.elapsed() << endl; double d; pt.restart(); iter found=find1(vec, vec.capacity()); d=pt.elapsed(); cout << "first search required: " << d << endl; cout << "first search found value: " << value_found(vec, found)<< endl; pt.restart(); found=find2(vec, vec.capacity()); d=pt.elapsed(); cout << "second search required: " << d << endl; cout << "second search found value: " << value_found(vec, found)<< endl; return 0; } On my machine (Intel i7, Windows Vista) STL find (call via find1) runs about 10 times faster than the hand-crafted loop (call via find2). I first thought that Visual C++ performs some kind of vectorization (may be I am mistaken here), but as far as I can see assembly does not look the way it uses vectorization. Why is STL loop faster? Hand-crafted loop is identical to the loop from the STL-find body. I was asked to post program's output. Without shuffle: value generation required: 0.078 first search required: 0.008 first search found value: no second search required: 0.098 second search found value: no With shuffle (caching effects): value generation required: 1.454 first search required: 0.009 first search found value: no second search required: 0.044 second search found value: no Many thanks, dusha. P.S. I return the iterator and write out the result (found or not), because I would like to prevent compiler optimization, that it thinks the loop is not required at all. The searched value is obviously not in the vector.

  Read the article

• map<string, vector<string>> reassignment of vector value

  - by user2950936

  I am trying to write a program that takes lines from an input file, sorts the lines into 'signatures' for the purpose of combining all words that are anagrams of each other. I have to use a map, storing the 'signatures' as the keys and storing all words that match those signatures into a vector of strings. Afterwards I must print all words that are anagrams of each other on the same line. Here is what I have so far: #include <iostream> #include <string> #include <algorithm> #include <map> #include <fstream> using namespace std; string signature(const string&); void printMap(const map<string, vector<string>>&); int main(){ string w1,sig1; vector<string> data; map<string, vector<string>> anagrams; map<string, vector<string>>::iterator it; ifstream myfile; myfile.open("words.txt"); while(getline(myfile, w1)) { sig1=signature(w1); anagrams[sig1]=data.push_back(w1); //to my understanding this should always work, } //either by inserting a new element/key or //by pushing back the new word into the vector<string> data //variable at index sig1, being told that the assignment operator //cannot be used in this way with these data types myfile.close(); printMap(anagrams); return 0; } string signature(const string& w) { string sig; sig=sort(w.begin(), w.end()); return sig; } void printMap(const map& m) { for(string s : m) { for(int i=0;i<m->second.size();i++) cout << m->second.at(); cout << endl; } } The first explanation is working, didn't know it was that simple! However now my print function is giving me: prob2.cc: In function âvoid printMap(const std::map<std::basic_string<char>, std::vector<std::basic_string<char> > >&)â: prob2.cc:43:36: error: cannot bind âstd::basic_ostream<char>::__ostream_type {aka std::basic_ostream<char>}â lvalue to âstd::basic_ostream<char>&&â In file included from /opt/centos/devtoolset-1.1/root/usr/lib/gcc/x86_64-redhat-linux/4.7.2/../../../../include/c++/4.7.2/iostream:40:0, Tried many variations and they always complain about binding void printMap(const map<string, vector<string>> &mymap) { for(auto &c : mymap) cout << c.first << endl << c.second << endl; }

  Read the article

• Scala: Recursively building all pathes in a graph?

  - by DarqMoth

  Trying to build all existing paths for an udirected graph defined as a map of edges using the following algorithm: Start: with a given vertice A Find an edge (X.A, X.B) or (X.B, X.A), add this edge to path Find all edges Ys fpr which either (Y.C, Y.B) or (Y.B, Y.C) is true For each Ys: A=B, goto Start Providing edges are defined as the following map, where keys are tuples consisting of two vertices: val edges = Map( ("n1", "n2") -> "n1n2", ("n1", "n3") -> "n1n3", ("n3", "n4") -> "n3n4", ("n5", "n1") -> "n5n1", ("n5", "n4") -> "n5n4") As an output I need to get a list of ALL pathes where each path is a list of adjecent edges like this: val allPaths = List( List(("n1", "n2") -> "n1n2"), List(("n1", "n3") -> "n1n3", ("n3", "n4") -> "n3n4"), List(("n5", "n1") -> "n5n1"), List(("n5", "n4") -> "n5n4"), List(("n2", "n1") -> "n1n2", ("n1", "n3") -> "n1n3", ("n3", "n4") -> "n3n4", ("n5", "n4") -> "n5n4")) //... //... more pathes to go } Note: Edge XY = (x,y) - "xy" and YX = (y,x) - "yx" exist as one instance only, either as XY or YX So far I have managed to implement code that duplicates edges in the path, which is wrong and I can not find the error: object Graph2 { type Vertice = String type Edge = ((String, String), String) type Path = List[((String, String), String)] val edges = Map( //(("v1", "v2") , "v1v2"), (("v1", "v3") , "v1v3"), (("v3", "v4") , "v3v4") //(("v5", "v1") , "v5v1"), //(("v5", "v4") , "v5v4") ) def main(args: Array[String]): Unit = { val processedVerticies: Map[Vertice, Vertice] = Map() val processedEdges: Map[(Vertice, Vertice), (Vertice, Vertice)] = Map() val path: Path = List() println(buildPath(path, "v1", processedVerticies, processedEdges)) } /** * Builds path from connected by edges vertices starting from given vertice * Input: map of edges * Output: list of connected edges like: List(("n1", "n2") -> "n1n2"), List(("n1", "n3") -> "n1n3", ("n3", "n4") -> "n3n4"), List(("n5", "n1") -> "n5n1"), List(("n5", "n4") -> "n5n4"), List(("n2", "n1") -> "n1n2", ("n1", "n3") -> "n1n3", ("n3", "n4") -> "n3n4", ("n5", "n4") -> "n5n4")) */ def buildPath(path: Path, vertice: Vertice, processedVerticies: Map[Vertice, Vertice], processedEdges: Map[(Vertice, Vertice), (Vertice, Vertice)]): List[Path] = { println("V: " + vertice + " VM: " + processedVerticies + " EM: " + processedEdges) if (!processedVerticies.contains(vertice)) { val edges = children(vertice) println("Edges: " + edges) val x = edges.map(edge => { if (!processedEdges.contains(edge._1)) { addToPath(vertice, processedVerticies.++(Map(vertice -> vertice)), processedEdges, path, edge) } else { println("ALready have edge: "+edge+" Return path:"+path) path } }) val y = x.toList y } else { List(path) } } def addToPath( vertice: Vertice, processedVerticies: Map[Vertice, Vertice], processedEdges: Map[(Vertice, Vertice), (Vertice, Vertice)], path: Path, edge: Edge): Path = { val newPath: Path = path ::: List(edge) val key = edge._1 val nextVertice = neighbor(vertice, key) val x = buildPath (newPath, nextVertice, processedVerticies, processedEdges ++ (Map((vertice, nextVertice) -> (vertice, nextVertice))) ).flatten // need define buidPath type x } def children(vertice: Vertice) = { edges.filter(p => (p._1)._1 == vertice || (p._1)._2 == vertice) } def containsPair(x: (Vertice, Vertice), m: Map[(Vertice, Vertice), (Vertice, Vertice)]): Boolean = { m.contains((x._1, x._2)) || m.contains((x._2, x._1)) } def neighbor(vertice: String, key: (String, String)): String = key match { case (`vertice`, x) => x case (x, `vertice`) => x } } Running this results in: List(List(((v1,v3),v1v3), ((v1,v3),v1v3), ((v3,v4),v3v4))) Why is that?

  Read the article

• How to generate a random unique string with more than 2^30 combination. I also wanted to reverse the process. Is this possible?

  - by Yusuf S

  I have a string which contains 3 elements: a 3 digit code (example: SIN, ABD, SMS, etc) a 1 digit code type (example: 1, 2, 3, etc) a 3 digit number (example: 500, 123, 345) Example string: SIN1500, ABD2123, SMS3345, etc.. I wanted to generate a UNIQUE 10 digit alphanumeric and case sensitive string (only 0-9/a-z/A-Z is allowed), with more than 2^30 (about 1 billion) unique combination per string supplied. The generated code must have a particular algorithm so that I can reverse the process. For example: public static void main(String[] args) { String test = "ABD2123"; String result = generateData(test); System.out.println(generateOutput(test)); //for example, the output of this is: 1jS8g4GDn0 System.out.println(generateOutput(result)); //the output of this will be ABD2123 (the original string supplied) } What I wanted to ask is is there any ideas/examples/libraries in java that can do this? Or at least any hint on what keyword should I put on Google? I tried googling using the keyword java checksum, rng, security, random number, etc and also tried looking at some random number solution (java SecureRandom, xorshift RNG, java.util.zip's checksum, etc) but I can't seem to find one? Thanks! EDIT: My use case for this program is to generate some kind of unique voucher number to be used by specific customers. The string supplied will contains 3 digit code for company ID, 1 digit code for voucher type, and a 3 digit number for the voucher nominal. I also tried adding 3 random alphanumeric (so the final digit is 7 + 3 digit = 10 digit). This is what I've done so far, but the result is not very good (only about 100 thousand combination): public static String in ="somerandomstrings"; public static String out="someotherrandomstrings"; public static String encrypt(String kata) throws Exception { String result=""; String ina=in; String outa=out; Random ran = new Random(); Integer modulus=in.length(); Integer offset= ((Integer.parseInt(Utils.convertDateToString(new Date(), "SS")))+ran.nextInt(60))/2%modulus; result=ina.substring(offset, offset+1); ina=ina+ina; ina=ina.substring(offset, offset+modulus); result=result+translate(kata, ina, outa); return result; } EDIT: I'm sorry I forgot to put the "translate" function : public static String translate(String kata,String seq1, String seq2){ String result=""; if(kata!=null&seq1!=null&seq2!=null){ String[] a=kata.split(""); for (int j = 1; j < a.length; j++) { String b=a[j]; String[]seq1split=seq1.split(""); String[]seq2split=seq2.split(""); int hint=seq1.indexOf(b)+1; String sq=""; if(seq1split.length>hint) sq=seq1split[hint]; String sq1=""; if(seq2split.length>hint) sq1=seq2split[hint]; b=b.replace(sq, sq1); result=result+b; } } return result; }

  Read the article

• Reconciling a new BindingList into a master BindingList using LINQ

  - by Neo

  I have a seemingly simple problem whereby I wish to reconcile two lists so that an 'old' master list is updated by a 'new' list containing updated elements. Elements are denoted by a key property. These are my requirements: All elements in either list that have the same key results in an assignment of that element from the 'new' list over the original element in the 'old' list only if any properties have changed. Any elements in the 'new' list that have keys not in the 'old' list will be added to the 'old' list. Any elements in the 'old' list that have keys not in the 'new' list will be removed from the 'old' list. I found an equivalent problem here - http://stackoverflow.com/questions/161432/ - but it hasn't really been answered properly. So, I came up with an algorithm to iterate through the old and new lists and perform the reconciliation as per the above. Before anyone asks why I'm not just replacing the old list object with the new list object in its entirety, it's for presentation purposes - this is a BindingList bound to a grid on a GUI and I need to prevent refresh artifacts such as blinking, scrollbars moving, etc. So the list object must remain the same, only its updated elements changed. Another thing to note is that the objects in the 'new' list, even if the key is the same and all the properties are the same, are completely different instances to the equivalent objects in the 'old' list, so copying references is not an option. Below is what I've come up with so far - it's a generic extension method for a BindingList. I've put comments in to demonstrate what I'm trying to do. public static class BindingListExtension { public static void Reconcile<T>(this BindingList<T> left, BindingList<T> right, string key) { PropertyInfo piKey = typeof(T).GetProperty(key); // Go through each item in the new list in order to find all updated and new elements foreach (T newObj in right) { // First, find an object in the new list that shares its key with an object in the old list T oldObj = left.First(call => piKey.GetValue(call, null).Equals(piKey.GetValue(newObj, null))); if (oldObj != null) { // An object in each list was found with the same key, so now check to see if any properties have changed and // if any have, then assign the object from the new list over the top of the equivalent element in the old list foreach (PropertyInfo pi in typeof(T).GetProperties()) { if (!pi.GetValue(oldObj, null).Equals(pi.GetValue(newObj, null))) { left[left.IndexOf(oldObj)] = newObj; break; } } } else { // The object in the new list is brand new (has a new key), so add it to the old list left.Add(newObj); } } // Now, go through each item in the old list to find all elements with keys no longer in the new list foreach (T oldObj in left) { // Look for an element in the new list with a key matching an element in the old list if (right.First(call => piKey.GetValue(call, null).Equals(piKey.GetValue(oldObj, null))) == null) { // A matching element cannot be found in the new list, so remove the item from the old list left.Remove(oldObj); } } } } It can be called like this: _oldBindingList.Reconcile(newBindingList, "MyKey") However, I'm looking for perhaps a method of doing the same using LINQ type methods such as GroupJoin<, Join<, Select<, SelectMany<, Intersect<, etc. So far, the problem I've had is that each of these LINQ type methods result in brand new intermediary lists (as a return value) and really, I only want to modify the existing list for all the above reasons. If anyone can help with this, would be most appreciated. If not, no worries, the above method (as it were) will suffice for now. Thanks, Jason

  Read the article

• Need a hand understanding this Java code please :-)

  - by Brian

  Hi all, Just wondering if anyone would be able to take a look at this code for implementing the quicksort algorithm and answer me a few questions, please :-) public class Run { /*************************************************************************** * Quicksort code from Sedgewick 7.1, 7.2. **************************************************************************/ public static void quicksort(double[] a) { //shuffle(a); // to guard against worst-case quicksort(a, 0, a.length - 1, 0); } static void quicksort(final double[] a, final int left, final int right, final int tdepth) { if (right <= left) return; final int i = partition(a, left, right); if ((tdepth < 4) && ((i - left) > 1000)) { final Thread t = new Thread() { public void run() { quicksort(a, left, i - 1, tdepth + 1); } }; t.start(); quicksort(a, i + 1, right, tdepth + 1); try { t.join(); } catch (InterruptedException e) { throw new RuntimeException("Cancelled", e); } } else { quicksort(a, left, i - 1, tdepth); quicksort(a, i + 1, right, tdepth); } } // partition a[left] to a[right], assumes left < right private static int partition(double[] a, int left, int right) { int i = left - 1; int j = right; while (true) { while (less(a[++i], a[right])) // find item on left to swap ; // a[right] acts as sentinel while (less(a[right], a[--j])) // find item on right to swap if (j == left) break; // don't go out-of-bounds if (i >= j) break; // check if pointers cross exch(a, i, j); // swap two elements into place } exch(a, i, right); // swap with partition element return i; } // is x < y ? private static boolean less(double x, double y) { return (x < y); } // exchange a[i] and a[j] private static void exch(double[] a, int i, int j) { double swap = a[i]; a[i] = a[j]; a[j] = swap; } // shuffle the array a[] private static void shuffle(double[] a) { int N = a.length; for (int i = 0; i < N; i++) { int r = i + (int) (Math.random() * (N - i)); // between i and N-1 exch(a, i, r); } } // test client public static void main(String[] args) { int N = 5000000; // Integer.parseInt(args[0]); // generate N random real numbers between 0 and 1 long start = System.currentTimeMillis(); double[] a = new double[N]; for (int i = 0; i < N; i++) a[i] = Math.random(); long stop = System.currentTimeMillis(); double elapsed = (stop - start) / 1000.0; System.out.println("Generating input: " + elapsed + " seconds"); // sort them start = System.currentTimeMillis(); quicksort(a); stop = System.currentTimeMillis(); elapsed = (stop - start) / 1000.0; System.out.println("Quicksort: " + elapsed + " seconds"); } } My questions are: What is the purpose of the variable tdepth? Is this considered a "proper" implementation of a parallel quicksort? I ask becuase it doesn't use implements Runnable or extends Thread... If it doesn't already, is it possible to modify this code to use multiple threads? By passing in the number of threads you want to use as a parameter, for example...? Many thanks, Brian

  Read the article

• Please help fix and optimize this query

  - by user607217

  I am working on a system to find potential duplicates in our customers table (SQL 2005). I am using the built-in SOUNDEX value that our software computes when customers are added/updated, but I also implemented the double metaphone algorithm for better matching. This is the most-nested query I have created, and I can't help but think there is a better way to do it and I'd like to learn. In the inner-most query I am joining the customer table to the metaphone table I created, then finding customers that have identical pKey (primary phonetic key). I take that, union that with customers that have matching soundex values, and then proceed to score those matches with various text similarity functions. This is currently working, but I would also like to add a union of customers whose aKey (alternate phonetic key) match. This would be identical to "QUERY A" except to substitute on (c1Akey = c2Akey) for the join. However, when I attempt to include that, I get errors when I try to execute my query. Here is the code: --Create aggregate ranking select c1Name, c2Name, nDiff, c1Addr, c2Addr, aDiff, c1SSN, c2SSN, sDiff, c1DOB, c2DOB, dDiff, nDiff+aDiff+dDiff+sDiff as Score ,(sDiff+dDiff)*1.5 + (nDiff+dDiff)*1.5 + (nDiff+sDiff)*1.5 + aDiff *.5 + nDiff *.5 as [Rank] FROM ( --Create match scores for different fields SELECT c1Name, c2Name, c1Addr, c2Addr, c1SSN, c2SSN, c1LTD, c2LTD, c1DOB, c2DOB, dbo.Jaro(c1name, c2name) AS nDiff, dbo.JaroWinkler(c1addr, c2addr) AS aDiff, CASE WHEN c1dob = '1901-01-01' OR c2dob = '1901-01-01' OR c1dob = '1800-01-01' OR c2dob = '1800-01-01' THEN .5 ELSE dbo.SmithWaterman(c1dob, c2dob) END AS dDiff, CASE WHEN c1ssn = '000-00-0000' OR c2ssn = '000-00-0000' THEN .5 ELSE dbo.Jaro(c1ssn, c2ssn) END AS sDiff FROM -- Generate list of possible matches based on multiple phonetic matching fields ( select * from -- List of similar names from pKey field of ##Metaphone table --QUERY A BEGIN (select customers.custno as c1Custno, name as c1Name, haddr as c1Addr, ssn as c1SSN, lasttripdate as c1LTD, dob as c1DOB, soundex as c1Soundex, pkey as c1Pkey, akey as c1Akey from Customers WITH (nolock) join ##Metaphone on customers.custno = ##Metaphone.custno) as c1 JOIN (select customers.custno as c2Custno, name as c2Name, haddr as c2Addr, ssn as c2SSN, lasttripdate as c2LTD, dob as c2DOB, soundex as c2Soundex, pkey as c2Pkey, akey as c2Akey from Customers with (nolock) join ##Metaphone on customers.custno = ##Metaphone.custno) as c2 on (c1Pkey = c2Pkey) and (c1Custno < c2Custno) WHERE (c1Name <> 'PARENT, GUARDIAN') and c1soundex != c2soundex --QUERY A END union --List of similar names from pregenerated SOUNDEX field (select t1.custno, t1.name, t1.haddr, t1.ssn, t1.lasttripdate, t1.dob, t1.[soundex], 0, 0, t2.custno, t2.name, t2.haddr, t2.ssn, t2.lasttripdate, t2.dob, t2.[soundex], 0, 0 from Customers t1 WITH (nolock) join customers t2 with (nolock) on t1.[soundex] = t2.[soundex] and t1.custno < t2.custno where (t1.name <> 'PARENT, GUARDIAN')) ) as a ) as b where (sDiff+dDiff)*1.5 + (nDiff+dDiff)*1.5 + (nDiff+sDiff)*1.5 + aDiff *.5 + nDiff *.5 >= 7.5 order by [rank] desc, score desc Previously, I was using joins such as on c1.pkey = c2.pkey or c1.akey = c2.akey or c1.soundex = c2.soundex but the performance was horrendous, and using unions seems to be working a lot better. Out of 103K customers, tt is currently generating a list of 8.5M potential matches (based on the phonetic codes) in 2.25 minutes, and then taking another 2 to score, rank and filter those down to about 3000. So I am happy with the performance, I just can't help but think there is a better way to structure this, and I need help adding the extra union condition. Thanks!

  Read the article

• Difficulty creating classes and arrays of those classes C#

  - by Lucifer Fayte

  I'm trying to implement a Discrete Fourier Transformation algorithm for a project I'm doing in school. But creating a class is seeming to be difficult(which it shouldn't be). I'm using Visual Studio 2012. Basically I need a class called Complex to store the two values I get from a DFT; The real portion and the imaginary portion. This is what I have so far for that: using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace SoundEditor_V3 { public class Complex { public double real; public double im; public Complex() { real = 0; im = 0; } } } The problem is that it doesn't recognize the constructor as a constructor, now I'm just learning C#, but I looked it up online and this is how it's supposed to look apparently. It recognizes my constructor as a method. Why is that? Am I creating the class wrong? It's doing the same thing for my Fourier class as well. So each time I try to create a Fourier object and then use it's method...there is no such thing. example, I do this: Fourier fou = new Fourier(); fou.DFT(s, N, amp, 0); and it tells me fou is a 'field' but is used like a 'type' why is it saying that? Here is the code for my Fourier class as well: using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace SoundEditor_V3 { public class Fourier { //FOURIER //N = number of samples //s is the array of samples(data) //amp is the array where the complex result will be written to //start is the where in the array to start public void DFT(byte[] s, int N, ref Complex[] amp, int start) { Complex tem = new Complex(); int f; int t; for (f = 0; f < N; f++) { tem.real = 0; tem.im = 0; for (t = 0; t < N; t++) { tem.real += s[t + start] * Math.Cos(2 * Math.PI * t * f / N); tem.im -= s[t + start] * Math.Sin(2 * Math.PI * t * f / N); } amp[f].real = tem.real; amp[f].im = tem.im; } } //INVERSE FOURIER public void IDFT(Complex[] A, ref int[] s) { int N = A.Length; int t, f; double result; for (t = 0; t < N; t++) { result = 0; for (f = 0; f < N; f++) { result += A[f].real * Math.Cos(2 * Math.PI * t * f / N) - A[f].im * Math.Sin(2 * Math.PI * t * f / N); } s[t] = (int)Math.Round(result); } } } } I'm very much stuck at the moment, any and all help would be appreciated. Thank you.

  Read the article

< Previous Page | 192 193 194 195 196 197 198 199 200 201 202 203  | Next Page >