The main purpose of this study is to evaluate the computational efficiency of algorithms for calculating shortest paths when they are correctly coded by using the C programming language. The eight algorithms that we selected for this experiment are the most efficient, either measured in terms of worst-case bounds or marked as such from previous computational studies; they include the redistributive heap algorithm. We suggest computer implementations that use the full power of C. In particular, the network representation and the various data structures used to keep the scan eligible list may be managed by using only additions and no multiplications, while it is not possible with FORTRAN. These capabilities, unique to C, yield several interesting conclusions: one may expect to speed up a shortest path algorithm by a factor of 20%; in some cases, this factor may reach 30%. Interestingly, the level of programming difficulty required to achieve these benefits is not greater than that required by implementations using arrays. 相似文献
This paper concerns the following problem: given a set of multi-attribute records, a fixed number of buckets and a two-disk system, arrange the records into the buckets and then store the buckets between the disks in such a way that, over all possible orthogonal range queries (ORQs), the disk access concurrency is maximized. We shall adopt the multiple key hashing (MKH) method for arranging records into buckets and use the disk modulo (DM) allocation method for storing buckets onto disks. Since the DM allocation method has been shown to be superior to any other allocation methods for allocating an MKH file onto a two-disk system for answering ORQs, the real issue is knowing how to determine an optimal way for organizing the records into buckets based upon the MKH concept.
A performance formula that can be used to evaluate the average response time, over all possible ORQs, of an MKH file in a two-disk system using the DM allocation method is first presented. Based upon this formula, it is shown that our design problem is related to a notoriously difficult problem, namely the Prime Number Problem. Then a performance lower bound and an efficient algorithm for designing optimal MKH files in certain cases are presented. It is pointed out that in some cases the optimal MKH file for ORQs in a two-disk system using the DM allocation method is identical to the optimal MKH file for ORQs in a single-disk system and the optimal average response time in a two-disk system is slightly greater than one half of that in a single-disk system. 相似文献
A circuit model for optical and electrical feedback has been developed to investigate the cause of negative differential resistance (NDR) switching in a series connected heterojunction phototransistor (HPT) light-emitting diode (LED) device. The model considers optical feedback from the light generated in the LED, electrical feedback from the holes thermally emitted over the LED cladding layer, nonlinear gain of the HPT, the Early effect, and leakage resistance. The analysis shows that either electrical or optical feedback can be the dominant cause for the NDR, depending upon their relative strengths. The NDR observed in the devices was caused primarily by electrical feedback since the optical feedback is weak. For low input power, avalanche breakdown appears to initiate the NDR in the devices although avalanching alone cannot cause NDR 相似文献
A novel soft decision-based median subtraction filter is presented for clutter suppression and infrared (IR) point targets enhancement. The decision is made based on a jump Markov model and its state and parameter estimation using a particle filter. The scheme is compared with other conventional clutter background removal techniques and good results are obtained. 相似文献
The fabrication and characterization of an integrated air-gap-capacitor pressure sensor are presented. The capacitor fabrication process uses standard IC processing to create NMOS circuits, and an added polysilicon layer to create poly-to-n+ capacitors with a 0.6-μm-thick dielectric using deposited oxide. Subsequent processing is used to produce deformable, parallel-plate, air-gap capacitors on the front side alongside MOS circuits. Sensor chips are fabricated using 100-μm×100-μm, 100-fF air-gap capacitors with on-chip circuitry. The sensor chip is a part of a capacitive measurement system that uses a charge-redistribution sense technique to achieve very high capacitance resolution. The behavior of the pressure sensor chips was studied as a function of applied pressure in the 0-240-kPa (0-35-psi) range. Measurements indicate a sensitivity of 0.93 mV/kPa (6.40 mV/psi) with a deflection of 10 nm/kPa (70 nm/psi) at 0-69 kPa (0-10 psi). Standard deviations indicate a static pressure resolution of 0.54 kPa (0.078 psi), which translates to 30 attofarads at a sampling frequency of 11 kHz 相似文献